QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#799300#667. Randomized Binary Search TreeKazemaruAC ✓1555ms16416kbC++171.7kb2024-12-05 10:17:302024-12-05 10:17:30

Judging History

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

  • [2024-12-05 10:17:30]
  • 评测
  • 测评结果:AC
  • 用时:1555ms
  • 内存:16416kb
  • [2024-12-05 10:17:30]
  • 提交

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=1e9;
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,p3=469762049;
	__int128 _=1,c1,c2,c3,u=_*p1*p2*p3;
	int n=2,m=0;for(;n<=s+l;n*=2)++m;
	f(i,s+1,n)a[i]=0;f(i,l+1,n)b[i]=0;
	mo=p1;m2=ksm(m3=3);c1=_*p2*p3*ksm(p2*p3%mo);
	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*p3*ksm(p1*p3%mo);
	f(i,0,n)a2[i]=a[i],b1[i]=b[i];mul(a2,b1,n,m);
	mo=p3;m2=ksm(m3=3);c3=_*p1*p2*ksm(p1*p2%mo);
	f(i,0,n)a3[i]=a[i],b1[i]=b[i];mul(a3,b1,n,m);
	f(i,0,n)a[i]=(a1[i]*c1+a2[i]*c2+a3[i]*c3)%u/V;
}
#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)g[i]=f[i];
		Kazemaru::mul_any(g,g,n,n);
		f(i,1,n)f[i]=g[i-1]/i;h[p]=f[n];
	}
	f(p,1,n)printf("%.5lf\n",(h[p]-h[p-1])*1.0/V);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 16416kb

input:

1

output:

1.00000

result:

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

Test #2:

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

input:

2

output:

0.00000
1.00000

result:

ok 2 numbers

Test #3:

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

input:

3

output:

0.00000
0.33333
0.66667

result:

ok 3 numbers

Test #4:

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

input:

4

output:

0.00000
0.00000
0.66667
0.33333

result:

ok 4 numbers

Test #5:

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

input:

5

output:

0.00000
0.00000
0.33333
0.53333
0.13333

result:

ok 5 numbers

Test #6:

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

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: 14360kb

input:

7

output:

0.00000
0.00000
0.01587
0.44444
0.40635
0.12063
0.01270

result:

ok 7 numbers

Test #8:

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

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: 2ms
memory: 16180kb

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: 13988kb

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: 0
Accepted
time: 1544ms
memory: 14700kb

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.00559
0.03472
0.10051
0.17051
0.19858
0.17720
0.13067
0.08...

result:

ok 30000 numbers

Test #12:

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

input:

56

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00001
0.00660
0.09098
0.24454
0.28157
0.20094
0.10628
0.04550
0.01650
0.00519
0.00144
0.00036
0.00008
0.00002
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.00...

result:

ok 56 numbers

Test #13:

score: 0
Accepted
time: 4ms
memory: 16172kb

input:

154

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00002
0.00314
0.04496
0.15814
0.24546
0.23170
0.15927
0.08826
0.04177
0.01746
0.00657
0.00226
0.00071
0.00021
0.00006
0.00001
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.00...

result:

ok 154 numbers

Test #14:

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

input:

230

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00081
0.01987
0.10226
0.20879
0.24088
0.19301
0.12121
0.06402
0.02966
0.01236
0.00470
0.00165
0.00054
0.00017
0.00005
0.00001
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 230 numbers

Test #15:

score: 0
Accepted
time: 6ms
memory: 16056kb

input:

198

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00006
0.00538
0.05505
0.16647
0.24199
0.22307
0.15300
0.08563
0.04126
0.01767
0.00685
0.00244
0.00080
0.00025
0.00007
0.00002
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 198 numbers

Test #16:

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

input:

274

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00004
0.00370
0.04219
0.14238
0.22789
0.22779
0.16740
0.09966
0.05090
0.02309
0.00950
0.00360
0.00126
0.00041
0.00013
0.00004
0.00001
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 274 numbers

Test #17:

score: 0
Accepted
time: 31ms
memory: 14184kb

input:

657

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.00004
0.00264
0.02985
0.11032
0.19873
0.22362
0.18367
0.12142
0.06865
0.03449
0.01577
0.00667
0.00263
0.00098
0.00034
0.00011
0.00004
0.00001
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 657 numbers

Test #18:

score: 0
Accepted
time: 31ms
memory: 14380kb

input:

628

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.00009
0.00435
0.03969
0.12750
0.20918
0.22085
0.17348
0.11099
0.06120
0.03012
0.01353
0.00563
0.00219
0.00080
0.00028
0.00009
0.00003
0.00001
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 628 numbers

Test #19:

score: 0
Accepted
time: 68ms
memory: 16064kb

input:

1319

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.00037
0.00849
0.05287
0.13938
0.20740
0.20994
0.16315
0.10522
0.05920
0.03000
0.01397
0.00607
0.00248
0.00096
0.00035
0.00012
0.00004
0.00001
0.00000
0.00000
0.00...

result:

ok 1319 numbers

Test #20:

score: 0
Accepted
time: 68ms
memory: 14140kb

input:

1453

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.00008
0.00326
0.03036
0.10488
0.18767
0.21582
0.18358
0.12650
0.07487
0.03953
0.01907
0.00854
0.00359
0.00142
0.00054
0.00019
0.00007
0.00002
0.00001
0.00000
0.00...

result:

ok 1453 numbers

Test #21:

score: 0
Accepted
time: 69ms
memory: 16288kb

input:

1095

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.00009
0.00383
0.03437
0.11387
0.19587
0.21754
0.17950
0.12041
0.06953
0.03585
0.01689
0.00739
0.00303
0.00117
0.00043
0.00015
0.00005
0.00002
0.00000
0.00000
0.00000
0.00...

result:

ok 1095 numbers

Test #22:

score: 0
Accepted
time: 737ms
memory: 14748kb

input:

15826

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.00004
0.00171
0.01723
0.06900
0.14547
0.19600
0.19285
0.15182
0.10175
0.06053
0.03287
0.01...

result:

ok 15826 numbers

Test #23:

score: 0
Accepted
time: 727ms
memory: 16092kb

input:

12332

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.00004
0.00163
0.01696
0.06894
0.14622
0.19718
0.19363
0.15188
0.10132
0.05996
0.03237
0.01625
0.00...

result:

ok 12332 numbers

Test #24:

score: 0
Accepted
time: 340ms
memory: 14484kb

input:

7285

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.00005
0.00196
0.01958
0.07626
0.15535
0.20207
0.19229
0.14673
0.09549
0.05522
0.02916
0.01432
0.00662
0.00290
0.00...

result:

ok 7285 numbers

Test #25:

score: 0
Accepted
time: 337ms
memory: 14192kb

input:

7621

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.00002
0.00115
0.01409
0.06315
0.14185
0.19763
0.19744
0.15605
0.10423
0.06149
0.03300
0.01642
0.00768
0.00340
0.00...

result:

ok 7621 numbers

Test #26:

score: 0
Accepted
time: 1555ms
memory: 14996kb

input:

27875

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.00002
0.00081
0.01054
0.05088
0.12342
0.18474
0.19684
0.16477
0.11593
0.07...

result:

ok 27875 numbers

Test #27:

score: 0
Accepted
time: 1550ms
memory: 14608kb

input:

29438

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.00039
0.00664
0.03853
0.10642
0.17459
0.19856
0.17419
0.12685
0.08...

result:

ok 29438 numbers

Test #28:

score: 0
Accepted
time: 1547ms
memory: 14416kb

input:

29062

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.00001
0.00047
0.00744
0.04127
0.11044
0.17720
0.19837
0.17206
0.12427
0.07...

result:

ok 29062 numbers

Test #29:

score: 0
Accepted
time: 1555ms
memory: 12776kb

input:

29415

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.00001
0.00040
0.00669
0.03870
0.10666
0.17475
0.19855
0.17406
0.12669
0.08...

result:

ok 29415 numbers

Test #30:

score: 0
Accepted
time: 1551ms
memory: 14964kb

input:

29394

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.00001
0.00040
0.00673
0.03885
0.10688
0.17490
0.19854
0.17394
0.12655
0.08...

result:

ok 29394 numbers

Test #31:

score: 0
Accepted
time: 1551ms
memory: 14300kb

input:

29485

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.00039
0.00655
0.03820
0.10592
0.17425
0.19857
0.17445
0.12717
0.08...

result:

ok 29485 numbers