QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#870669#667. Randomized Binary Search TreeCarroT1212WA 2313ms9696kbC++143.1kb2025-01-25 17:19:032025-01-25 17:19:05

Judging History

你现在查看的是最新测评结果

  • [2025-01-25 17:19:05]
  • 评测
  • 测评结果:WA
  • 用时:2313ms
  • 内存:9696kb
  • [2025-01-25 17:19:03]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using lll=__int128;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,K=1e9,N=6e4+7,P[3]={469762049,998244353,1004535809};
ll O;
namespace FPS {
	inline ll add(ll x,ll y){return(x+=y)<P[O]?x:x-P[O];}
	inline ll dec(ll x,ll y){return(x-=y)>=0?x:x+P[O];}
	inline ll qpow(ll x,ll y,ll mul=1){while(y)mul=y&1?mul*x%P[O]:mul,x=x*x%P[O],y>>=1;return mul;}
	ll N;
	vector<ll> rev;
	inline void NTT_init(ll n) {
		if (N>=n&&N<n<<1) return;
		ll c=-1; N=1; while (N<n) N<<=1,c++;
		if (N>rev.size()) rev.resize(N);
		for (ll i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
	}
	struct fps:vector<ll> {
		friend fps operator * (fps f,fps g) {
			static ll t;
			t=f.size()+g.size()-1;
			if (min(f.size(),g.size())<=40) {
				fps ret(t);
				for (ll i=0;i<f.size();i++) for (ll j=0;j<g.size();j++)
					ret[i+j]=(ret[i+j]+f[i]*g[j])%P[O];
				return ret;
			}
			NTT_init(t),f.NTT(1),g.NTT(1);
			for (ll i=0;i<N;i++) f[i]=f[i]*g[i]%P[O];
			f.NTT(-1);
			return f.pre(t);
		}
		#define f (*this)
		using vector<ll>::vector;
		inline fps pre(ll n) { return fps(f.begin(),f.begin()+min((ll)f.size(),n)); }
		void NTT(ll op) {
			f.resize(N);
			for (ll i=0;i<N;i++) if (i<rev[i]) ::swap(f[i],f[rev[i]]);
			for (ll i=1;i<N;i<<=1) {
				ll w1=qpow(op==1?3:qpow(3,P[O]-2),(P[O]-1)/(i<<1));
				for (ll j=0;j<N;j+=i<<1) for (ll k=j,w=1;k<j+i;k++,w=w*w1%P[O]) {
					ll t1=f[k],t2=w*f[k+i]%P[O];
					f[k]=add(t1,t2),f[k+i]=dec(t1,t2);
				}
			}
			if (op==-1) {
				ll inv=qpow(N,P[O]-2);
				for (ll i=0;i<N;i++) f[i]=f[i]*inv%P[O];
			}
		}
		#undef f
	};
} using FPS::fps;
lll PP[3];
fps a,b;
void ecd(lll a,lll b,lll &x,lll &y) { b?(ecd(b,a%b,y,x),y-=a/b*x):(x=1,y=0); }
lll ert(ll n,lll *m,lll *a) {
	for (ll i=1;i<n;i++) {
		lll g=__gcd(m[i],m[0]),f=a[i]-a[0],p,q;
		if (f%g!=0) return -1;
		m[i]/=g,ecd(m[0]/g,m[i],p,q);
		a[0]+=f/g*p%m[i]*m[0],m[0]*=m[i],a[0]%=m[0];
	}
	return (a[0]%m[0]+m[0])%m[0];
}
struct fsp {
	fps f[3];
	void sz(ll n) { for (ll o=0;o<3;o++) f[o].resize(n); }
	friend fsp operator * (fsp x,fsp y) {
		fsp z;
		for (ll o=0;o<3;o++) O=o,z.f[o]=x.f[o]*y.f[o];
		return z;
	}
	void set(ll x,ll y) { for (ll o=0;o<3;o++) f[o][x]=y%P[o]; }
	fps get() {
		ll n=f[0].size(); fps ret(n);
		for (ll i=0;i<n;i++) {
			lll a[3]={f[0][i],f[1][i],f[2][i]};
			for (ll o=0;o<3;o++) PP[o]=P[o];
			ret[i]=ert(3,PP,a)/K;
		}
		return ret;
	}
} A;
ll n,ans[N];
void mian() {
	scanf("%lld",&n);
	ll t=1;
	A.sz(t),A.set(0,K);
	for (ll o=1;o<=min(n,42ll);o++) {
		A=A*A,t=t*2,t=min(t,n);
		A.sz(t+1);
		fps f=A.get();
		for (ll i=t;i;i--) f[i]=f[i-1]/i;
		if (t==n) ans[o]=f[n];
		for (ll i=0;i<=t;i++) A.set(i,f[i]);
	}
	for (ll o=43;o<=n;o++) ans[o]=K;
	for (ll i=0;i<n;i++) printf("%.10Lf\n",(ld)(ans[i+1]-ans[i])/K);
}
bool ORY; int main() {
//	while (1)
//	int t; for (scanf("%d",&t);t--;)
	mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3840kb

input:

1

output:

1.0000000000

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3968kb

input:

2

output:

0.0000000000
1.0000000000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

3

output:

0.0000000000
0.3333333330
0.6666666670

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

4

output:

0.0000000000
0.0000000000
0.6666666660
0.3333333340

result:

ok 4 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

5

output:

0.0000000000
0.0000000000
0.3333333330
0.5333333330
0.1333333340

result:

ok 5 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

6

output:

0.0000000000
0.0000000000
0.1111111110
0.5555555550
0.2888888890
0.0444444450

result:

ok 6 numbers

Test #7:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

7

output:

0.0000000000
0.0000000000
0.0158730150
0.4444444450
0.4063492060
0.1206349210
0.0126984130

result:

ok 7 numbers

Test #8:

score: 0
Accepted
time: 1ms
memory: 3968kb

input:

8

output:

0.0000000000
0.0000000000
0.0000000000
0.2817460310
0.4666666670
0.2071428570
0.0412698410
0.0031746040

result:

ok 8 numbers

Test #9:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

9

output:

0.0000000000
0.0000000000
0.0000000000
0.1516754840
0.4650793650
0.2878306880
0.0827160500
0.0119929450
0.0007054680

result:

ok 9 numbers

Test #10:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

10

output:

0.0000000000
0.0000000000
0.0000000000
0.0698412690
0.4155731920
0.3520634920
0.1320105820
0.0273368610
0.0030335100
0.0001410940

result:

ok 10 numbers

Test #11:

score: -100
Wrong Answer
time: 2313ms
memory: 9696kb

input:

30000

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

wrong answer 43rd numbers differ - expected: '0.00276', found: '0.00479', error = '0.00203'