QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#799300 | #667. Randomized Binary Search Tree | Kazemaru | AC ✓ | 1555ms | 16416kb | C++17 | 1.7kb | 2024-12-05 10:17:30 | 2024-12-05 10:17:30 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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