QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#870675 | #667. Randomized Binary Search Tree | CarroT1212 | TL | 1ms | 3968kb | C++14 | 3.1kb | 2025-01-25 17:20:28 | 2025-01-25 17:20:37 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using lll=__int128;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,K=1e9,N=6e4+7,P[3]={469762049,998244353,1004535809};
ll O;
namespace FPS {
inline ll add(ll x,ll y){return(x+=y)<P[O]?x:x-P[O];}
inline ll dec(ll x,ll y){return(x-=y)>=0?x:x+P[O];}
inline ll qpow(ll x,ll y,ll mul=1){while(y)mul=y&1?mul*x%P[O]:mul,x=x*x%P[O],y>>=1;return mul;}
ll N;
vector<ll> rev;
inline void NTT_init(ll n) {
if (N>=n&&N<n<<1) return;
ll c=-1; N=1; while (N<n) N<<=1,c++;
if (N>rev.size()) rev.resize(N);
for (ll i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
}
struct fps:vector<ll> {
friend fps operator * (fps f,fps g) {
static ll t;
t=f.size()+g.size()-1;
if (min(f.size(),g.size())<=40) {
fps ret(t);
for (ll i=0;i<f.size();i++) for (ll j=0;j<g.size();j++)
ret[i+j]=(ret[i+j]+f[i]*g[j])%P[O];
return ret;
}
NTT_init(t),f.NTT(1),g.NTT(1);
for (ll i=0;i<N;i++) f[i]=f[i]*g[i]%P[O];
f.NTT(-1);
return f.pre(t);
}
#define f (*this)
using vector<ll>::vector;
inline fps pre(ll n) { return fps(f.begin(),f.begin()+min((ll)f.size(),n)); }
void NTT(ll op) {
f.resize(N);
for (ll i=0;i<N;i++) if (i<rev[i]) ::swap(f[i],f[rev[i]]);
for (ll i=1;i<N;i<<=1) {
ll w1=qpow(op==1?3:qpow(3,P[O]-2),(P[O]-1)/(i<<1));
for (ll j=0;j<N;j+=i<<1) for (ll k=j,w=1;k<j+i;k++,w=w*w1%P[O]) {
ll t1=f[k],t2=w*f[k+i]%P[O];
f[k]=add(t1,t2),f[k+i]=dec(t1,t2);
}
}
if (op==-1) {
ll inv=qpow(N,P[O]-2);
for (ll i=0;i<N;i++) f[i]=f[i]*inv%P[O];
}
}
#undef f
};
} using FPS::fps;
lll PP[3];
fps a,b;
void ecd(lll a,lll b,lll &x,lll &y) { b?(ecd(b,a%b,y,x),y-=a/b*x):(x=1,y=0); }
lll ert(ll n,lll *m,lll *a) {
for (ll i=1;i<n;i++) {
lll g=__gcd(m[i],m[0]),f=a[i]-a[0],p,q;
if (f%g!=0) return -1;
m[i]/=g,ecd(m[0]/g,m[i],p,q);
a[0]+=f/g*p%m[i]*m[0],m[0]*=m[i],a[0]%=m[0];
}
return (a[0]%m[0]+m[0])%m[0];
}
struct fsp {
fps f[3];
void sz(ll n) { for (ll o=0;o<3;o++) f[o].resize(n); }
friend fsp operator * (fsp x,fsp y) {
fsp z;
for (ll o=0;o<3;o++) O=o,z.f[o]=x.f[o]*y.f[o];
return z;
}
void set(ll x,ll y) { for (ll o=0;o<3;o++) f[o][x]=y%P[o]; }
fps get() {
ll n=f[0].size(); fps ret(n);
for (ll i=0;i<n;i++) {
lll a[3]={f[0][i],f[1][i],f[2][i]};
for (ll o=0;o<3;o++) PP[o]=P[o];
ret[i]=ert(3,PP,a)/K;
}
return ret;
}
} A;
const ll B=46;
ll n,ans[N];
void mian() {
scanf("%lld",&n);
ll t=1;
A.sz(t),A.set(0,K);
for (ll o=1;o<=min(n,B);o++) {
A=A*A,t=t*2,t=min(t,n);
A.sz(t+1);
fps f=A.get();
for (ll i=t;i;i--) f[i]=f[i-1]/i;
if (t==n) ans[o]=f[n];
for (ll i=0;i<=t;i++) A.set(i,f[i]);
}
for (ll o=B+1;o<=n;o++) ans[o]=K;
for (ll i=0;i<n;i++) printf("%.10Lf\n",(ld)(ans[i+1]-ans[i])/K);
}
bool ORY; int main() {
// while (1)
// int t; for (scanf("%d",&t);t--;)
mian();
cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3968kb
input:
1
output:
1.0000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
2
output:
0.0000000000 1.0000000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
3
output:
0.0000000000 0.3333333330 0.6666666670
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
4
output:
0.0000000000 0.0000000000 0.6666666660 0.3333333340
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
5
output:
0.0000000000 0.0000000000 0.3333333330 0.5333333330 0.1333333340
result:
ok 5 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
6
output:
0.0000000000 0.0000000000 0.1111111110 0.5555555550 0.2888888890 0.0444444450
result:
ok 6 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
7
output:
0.0000000000 0.0000000000 0.0158730150 0.4444444450 0.4063492060 0.1206349210 0.0126984130
result:
ok 7 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
8
output:
0.0000000000 0.0000000000 0.0000000000 0.2817460310 0.4666666670 0.2071428570 0.0412698410 0.0031746040
result:
ok 8 numbers
Test #9:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
9
output:
0.0000000000 0.0000000000 0.0000000000 0.1516754840 0.4650793650 0.2878306880 0.0827160500 0.0119929450 0.0007054680
result:
ok 9 numbers
Test #10:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
10
output:
0.0000000000 0.0000000000 0.0000000000 0.0698412690 0.4155731920 0.3520634920 0.1320105820 0.0273368610 0.0030335100 0.0001410940
result:
ok 10 numbers
Test #11:
score: -100
Time Limit Exceeded
input:
30000