QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799344 | #667. Randomized Binary Search Tree | Kazemaru | AC ✓ | 1543ms | 16420kb | C++17 | 1.6kb | 2024-12-05 11:26:33 | 2024-12-05 11:26:34 |
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)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);f(i,0,n)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;
h(i,0,n,1)r[i]=i?(r[i>>1]>>1)|((i&1)<<m):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])*1e-9);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 14132kb
input:
1
output:
1.00000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 13956kb
input:
2
output:
0.00000 1.00000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 14304kb
input:
3
output:
0.00000 0.33333 0.66667
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 14224kb
input:
4
output:
0.00000 0.00000 0.66667 0.33333
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 2ms
memory: 14300kb
input:
5
output:
0.00000 0.00000 0.33333 0.53333 0.13333
result:
ok 5 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 14228kb
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: 0ms
memory: 13992kb
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: 1ms
memory: 13992kb
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: 1ms
memory: 14164kb
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: 14000kb
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: 1543ms
memory: 14748kb
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: 4ms
memory: 14016kb
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: 6ms
memory: 14140kb
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: 9ms
memory: 14228kb
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: 9ms
memory: 14236kb
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: 17ms
memory: 14280kb
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: 33ms
memory: 14376kb
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: 26ms
memory: 14360kb
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: 72ms
memory: 14156kb
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: 72ms
memory: 16420kb
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: 67ms
memory: 14372kb
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: 760ms
memory: 14508kb
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: 724ms
memory: 14048kb
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: 337ms
memory: 14220kb
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: 14480kb
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: 1533ms
memory: 14796kb
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: 1541ms
memory: 14456kb
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: 1542ms
memory: 14612kb
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: 1543ms
memory: 14676kb
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: 1531ms
memory: 14756kb
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: 1540ms
memory: 16128kb
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