QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#799299#667. Randomized Binary Search TreeKazemaruWA 1050ms16564kbC++171.5kb2024-12-05 10:13:462024-12-05 10:13:46

Judging History

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

  • [2024-12-05 10:13:46]
  • 评测
  • 测评结果:WA
  • 用时:1050ms
  • 内存:16564kb
  • [2024-12-05 10:13:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
const int N=2e5,V=1e6;
namespace Kazemaru{
int a1[N],a2[N],a3[N],b1[N],r[N],mo,m2,m3;
#define h(a,b,c,d) for(int a=b;a<c;a+=d)
inline int ksm(int x,int p=mo-2,int y=1){for(;p;p/=2,x=x*x%mo)if(p&1)y=x*y%mo;return y;}
inline int Add(int x,int y){return (x+=y)>=mo?x-mo:x;}
inline void NTT(int*f,int n,int m,int p){
	int k,g,u,v,w,len,ny=ksm(n);
	h(i,0,n,1)r[i]=i?(r[i>>1]>>1)|((i&1)<<m):0;
	h(i,0,n,1)if(i<r[i])swap(f[i],f[r[i]]);
	h(l,1,n,l){
		len=l*2;k=len/2;g=ksm(p?m2:m3,(mo-1)/len);
		h(i,0,n*(w=1),len)h(j,0,k,1){
			u=f[i+j];v=f[i+j+k]*w%mo;
			f[i+j]=Add(u,v);f[i+j+k]=Add(u-v,mo);
			w=w*g%mo;
		}
	}
	if(p)h(i,0,n,1)f[i]=f[i]*ny%mo;
}
inline void mul(int*a,int*b,int n,int m){NTT(a,n,m,0);NTT(b,n,m,0);h(i,0,n,1)a[i]=a[i]*b[i]%mo;NTT(a,n,m,1);}
inline void mul_any(int*a,int*b,int s,int l){
	int p1=998244353,p2=1004535809;
	__int128 _=1,c1,c2,u=_*p1*p2;
	int n=2,m=0;
	for(;n<=s+l;n*=2)++m;
	mo=p1;m2=ksm(m3=3);c1=_*p2*ksm(p2);
	f(i,0,n)a1[i]=a[i],b1[i]=b[i];mul(a1,b1,n,m);
	mo=p2;m2=ksm(m3=3);c2=_*p1*ksm(p1);
	f(i,0,n)a2[i]=a[i],b1[i]=b[i];mul(a2,b1,n,m);
	f(i,0,n)a[i]=(a1[i]*c1+a2[i]*c2)%u;
}
#undef h
}
int f[N],g[N],h[N];
signed main(){
	cin>>n;f[0]=V;
	f(p,1,n){
		if(p>50){h[p]=V;continue;}
		f(i,0,n*2)g[i]=i>n?0:f[i];
		Kazemaru::mul_any(g,g,n,n);
		f(i,1,n)f[i]=g[i-1]/V/i;h[p]=f[n];
	}
	f(p,1,n)printf("%.5lf\n",(h[p]-h[p-1])*1.0/V);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 14264kb

input:

1

output:

1.00000

result:

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

Test #2:

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

input:

2

output:

0.00000
1.00000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 14156kb

input:

3

output:

0.00000
0.33333
0.66667

result:

ok 3 numbers

Test #4:

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

input:

4

output:

0.00000
0.00000
0.66667
0.33333

result:

ok 4 numbers

Test #5:

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

input:

5

output:

0.00000
0.00000
0.33333
0.53333
0.13333

result:

ok 5 numbers

Test #6:

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

input:

6

output:

0.00000
0.00000
0.11111
0.55556
0.28889
0.04444

result:

ok 6 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 13948kb

input:

7

output:

0.00000
0.00000
0.01587
0.44444
0.40635
0.12064
0.01270

result:

ok 7 numbers

Test #8:

score: 0
Accepted
time: 2ms
memory: 14004kb

input:

8

output:

0.00000
0.00000
0.00000
0.28175
0.46667
0.20714
0.04127
0.00317

result:

ok 8 numbers

Test #9:

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

input:

9

output:

0.00000
0.00000
0.00000
0.15168
0.46508
0.28783
0.08272
0.01199
0.00071

result:

ok 9 numbers

Test #10:

score: 0
Accepted
time: 2ms
memory: 13956kb

input:

10

output:

0.00000
0.00000
0.00000
0.06984
0.41557
0.35206
0.13201
0.02734
0.00303
0.00014

result:

ok 10 numbers

Test #11:

score: -100
Wrong Answer
time: 1050ms
memory: 16564kb

input:

30000

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00030
0.00558
0.03466
0.10035
0.17026
0.19831
0.17699
0.13053
0.08...

result:

wrong answer 31st numbers differ - expected: '0.00559', found: '0.00558', error = '0.00001'