QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799299 | #667. Randomized Binary Search Tree | Kazemaru | WA | 1050ms | 16564kb | C++17 | 1.5kb | 2024-12-05 10:13:46 | 2024-12-05 10:13:46 |
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=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;
}
详细
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'