QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#852566 | #667. Randomized Binary Search Tree | liyujia | AC ✓ | 1224ms | 9216kb | C++14 | 5.2kb | 2025-01-11 12:49:06 | 2025-01-11 12:49:08 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define ll __int128
using namespace std;
namespace FPS{
int N;
vector<int> rev,_inv = {0,1};
template <const int mod = 998244353>
struct fps: vector<int>{
void NTT_init(int n){ //NTT 前将次数扩增成 2 的幂,预处理 rev[] 数组
if(N >= n && N < (n << 1)) return;
int c = -1;
N = 1;
while(N < n) N <<= 1,c ++;
if(N > rev.size()) rev.resize(N);
for(int i = 0; i < N; i ++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << c);
}
void inv_init(int n){ //预处理
int t = _inv.size();
if(n > t) _inv.resize(n);
for(int i = t; i < n; i ++) _inv[i] = 1ll * _inv[mod % i] * dec(0,mod / i) % mod;
}
int add(int x,int y){
x += y;
return x < mod ? x : x - mod;
}
int dec(int x,int y){
x -= y;
return x >= 0 ? x : x + mod;
}
int qpow(int x,int k){
int d = 1;
while(k){
if(k & 1) d = 1ll * d * x % mod;
x = 1ll * x * x % mod,k >>= 1;
}
return d;
}
friend fps operator * (fps f,fps g){ // 返回 f * g
static int t;
t = f.size() + g.size() - 1;
if(min(f.size(),g.size()) <= 40){
fps ret(t);
for(int i = 0; i < f.size(); i ++)
for(int j = 0; j < g.size(); j ++)
ret[i + j] = (ret[i + j] + 1ll * f[i] * g[j]) % mod;
return ret;
}
f.NTT_init(t);
f.NTT(1),g.NTT(1);
for(int i = 0; i < N; i ++) f[i] = 1ll * f[i] * g[i] % mod;
f.NTT(-1);
return f.pre(t);
}
friend fps operator + (fps f,fps g){ // 多项式加法
if(f.size() < g.size()) f.swap(g);
for(int i = 0; i < g.size(); i ++) f[i] = add(f[i],g[i]);
return f;
}
friend fps operator - (fps f,fps g){ // 多项式减法
if(f.size() < g.size()) f.resize(g.size());
for(int i = 0; i < g.size(); i ++) f[i] = dec(f[i],g[i]);
return f;
}
#define f (*this)
using vector<int>::vector;
inline fps pre(int n){
return fps(f.begin(),f.begin() + min((int)f.size(),n));
}
void NTT(int op){ // NTT,op = 1 表示正变换,否则逆变换
f.resize(N);
int g = qpow(3, mod - 2);
for(int i = 0; i < N; i ++) if(i < rev[i]) ::swap(f[i],f[rev[i]]);
for(int i = 1; i < N; i <<= 1){
int w1 = qpow(op == 1 ? 3 : g,(mod - 1) / (i << 1));
for(int j = 0; j < N; j += i << 1){
int w = 1;
for(int k = j; k < j + i; k ++){
int t1 = f[k],t2 = 1ll * w * f[k + i] % mod;
f[k] = add(t1,t2),f[k + i] = dec(t1,t2);
w = 1ll * w * w1 % mod;
}
}
}
if(op == -1){
int iv = qpow(N,mod - 2);
for(int i = 0; i < N; i ++) f[i] = 1ll * f[i] * iv % mod;
}
}
fps inv(int n = 0){ // f.inv(n) 返回 1/f(x) mod x^n,n=0 时默认为 f.size()
if(!n) n = f.size();
fps g = {qpow(f[0],mod - 2)},h;
int d = 1;
while(d < n){
d <<= 1;
NTT_init(d << 1),h = f.pre(d);
g.NTT(1),h.NTT(1);
for(int i = 0; i < N; i ++) g[i] = 1ll * g[i] * dec(2,1ll * h[i] * g[i] % mod) % mod;
g.NTT(-1),g.resize(d);
}
return g.pre(n);
}
fps ln(int n = 0){ // 调用 f.ln(n) 返回 ln(f(x)) mod x^n,n=0 时默认为 f.size(),需保证 f[0] = 1
if(!n) n = f.size();
fps h = f.pre(n);
for(int i = 0; i + 1 < h.size(); i ++) h[i] = 1ll * (i + 1) * h[i + 1] % mod;
h.pop_back();
h = (h * f.inv(n + 1)).pre(n);
inv_init(n);
for(int i = n - 1; i >= 1; i --) h[i] = 1ll * h[i - 1] * _inv[i] % mod;
h[0] = 0;
return h;
}
fps exp(int n = 0){ // 调用 f.exp(n) 返回 exp(f(x)) mod x^n,n=0 时默认为 f.size(),需保证 f[0] = 0
if(!n) n = f.size();
fps g = {1};
int d = 1;
while(d < n){
d <<= 1;
g = g * (fps{1} + f.pre(d) - g.ln(d));
}
return g.pre(n);
}
void in(int n){
int x;
for(int i = 1; i <= n; i++) cin >> x, f.push_back(x);
}
void out(){
for(int x: f) cout << x << ' ';
cout << '\n';
}
fps(vector <int> x){ f.resize(x.size()); for(int i = 0; i < x.size(); i++) f[i] = x[i] % mod;}
#undef f
};
}
using FPS::fps;
int read(){
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') x = x * 10 + (c ^ 48),c = getchar();
return x * f;
}
fps<> calc(vector<fps<>> &v,int l,int r){
if(l == r) return v[l];
int mid = (l + r) >> 1;
return calc(v,l,mid) * calc(v,mid + 1,r);
}
const int m1 = 998244353, m2 = 1004535809, m3 = 104857601;
ll qpow(ll x, ll y, ll p){
if(!y) return 1;
return qpow(x * x % p, y >> 1, p) * (y & 1? x: 1) % p;
}
const int N = 50005, V = 1e10;
ll ans[N], g[N];
int n;
signed main(){
cin >> n;
vector <int> f(n + 1);
f[0] = V;
for(int i = 1; i <= n; i++){
if(i > 50){ ans[i] = V; continue;}
fps <m1> f1(f); fps <m2> f2(f); fps <m3> f3(f);
f1 = f1 * f1, f2 = f2 * f2, f3 = f3 * f3;
ll p = (ll)m1 * m2 * m3, c1 = (ll)m2 * m3 * qpow(m2 * m3 % m1, m1 - 2, m1), c2 = (ll)m1 * m3 * qpow(m1 * m3 % m2, m2 - 2, m2), c3 = (ll)m2 * m1 * qpow(m2 * m1 % m3, m3 - 2, m3);
for(int j = 1; j <= n; j++) f[j] = (f1[j - 1] * c1 + f2[j - 1] * c2 + f3[j - 1] * c3) % p / V / j;
ans[i] = f[n];
}
for(int i = 1; i <= n; i++) cout << fixed << setprecision(10) << 1. * (ans[i] - ans[i - 1]) / V << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
1
output:
1.0000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
2
output:
0.0000000000 1.0000000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
3
output:
0.0000000000 0.3333333333 0.6666666667
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
4
output:
0.0000000000 0.0000000000 0.6666666666 0.3333333334
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
5
output:
0.0000000000 0.0000000000 0.3333333333 0.5333333333 0.1333333334
result:
ok 5 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
6
output:
0.0000000000 0.0000000000 0.1111111111 0.5555555555 0.2888888889 0.0444444445
result:
ok 6 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
7
output:
0.0000000000 0.0000000000 0.0158730158 0.4444444444 0.4063492064 0.1206349206 0.0126984128
result:
ok 7 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
8
output:
0.0000000000 0.0000000000 0.0000000000 0.2817460317 0.4666666666 0.2071428572 0.0412698413 0.0031746032
result:
ok 8 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
9
output:
0.0000000000 0.0000000000 0.0000000000 0.1516754849 0.4650793651 0.2878306878 0.0827160494 0.0119929454 0.0007054674
result:
ok 9 numbers
Test #10:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
10
output:
0.0000000000 0.0000000000 0.0000000000 0.0698412698 0.4155731922 0.3520634920 0.1320105821 0.0273368607 0.0030335097 0.0001410935
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 1224ms
memory: 9152kb
input:
30000
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0...
result:
ok 30000 numbers
Test #12:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
56
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000100557 0.0066028117 0.0909815584 0.2445350359 0.2815705990 0.2009351482 0.1062773161 0.0455017452 0.0164975773 0.0051931410 0.0014409273 0.0003560094 0.0000788969 0.0000157704 0.0000028556 0.0000004701 0.0000000705 0...
result:
ok 56 numbers
Test #13:
score: 0
Accepted
time: 6ms
memory: 3860kb
input:
154
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000001 0.0000155438 0.0031401501 0.0449621343 0.1581448049 0.2454594167 0.2316969544 0.1592686489 0.0882569293 0.0417681120 0.0174554021 0.0065726693 0.0022587185 0.0007146727 0.0002095371 0...
result:
ok 154 numbers
Test #14:
score: 0
Accepted
time: 6ms
memory: 3736kb
input:
230
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000018718 0.0008132811 0.0198650746 0.1022596067 0.2087920502 0.2408796290 0.1930144419 0.1212070442 0.0640239983 0.0296596825 0.0123571691 0.0047036698 0.0016528709 0...
result:
ok 230 numbers
Test #15:
score: 0
Accepted
time: 6ms
memory: 3828kb
input:
198
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000078 0.0000599465 0.0053761760 0.0550507271 0.1664660869 0.2419855575 0.2230725767 0.1529980733 0.0856275679 0.0412593784 0.0176668104 0.0068534824 0.0024388244 0.0008029022 0...
result:
ok 198 numbers
Test #16:
score: 0
Accepted
time: 12ms
memory: 3892kb
input:
274
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000071 0.0000397088 0.0037043879 0.0421940434 0.1423796265 0.2278857747 0.2277852434 0.1674036174 0.0996564755 0.0509034345 0.0230927641 0.0095035674 0.0035962841 0...
result:
ok 274 numbers
Test #17:
score: 0
Accepted
time: 25ms
memory: 3976kb
input:
657
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000248 0.0000386334 0.0026437821 0.0298522454 0.1103163563 0.1987327379 0.2236216124 0.1836742336 0.1214160897 0.0686546862 0...
result:
ok 657 numbers
Test #18:
score: 0
Accepted
time: 25ms
memory: 3928kb
input:
628
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000001039 0.0000895312 0.0043520589 0.0396869812 0.1275012543 0.2091798605 0.2208537928 0.1734787216 0.1109908337 0.0611968966 0...
result:
ok 628 numbers
Test #19:
score: 0
Accepted
time: 48ms
memory: 3860kb
input:
1319
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000002 0.0000019368 0.0003656493 0.0084871499 0.0528665487 0.1393765245 0.2073961978 0.2099387638 0...
result:
ok 1319 numbers
Test #20:
score: 0
Accepted
time: 51ms
memory: 3976kb
input:
1453
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000001510 0.0000762447 0.0032639724 0.0303620603 0.1048848814 0.1876730086 0.2158244970 0...
result:
ok 1453 numbers
Test #21:
score: 0
Accepted
time: 50ms
memory: 3992kb
input:
1095
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000001678 0.0000906210 0.0038326480 0.0343697843 0.1138738925 0.1958723714 0.2175354432 0.1795025807 0...
result:
ok 1095 numbers
Test #22:
score: 0
Accepted
time: 572ms
memory: 6252kb
input:
15826
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0...
result:
ok 15826 numbers
Test #23:
score: 0
Accepted
time: 552ms
memory: 5980kb
input:
12332
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0...
result:
ok 12332 numbers
Test #24:
score: 0
Accepted
time: 251ms
memory: 4708kb
input:
7285
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000001466 0...
result:
ok 7285 numbers
Test #25:
score: 0
Accepted
time: 261ms
memory: 4732kb
input:
7621
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000403 0...
result:
ok 7621 numbers
Test #26:
score: 0
Accepted
time: 1195ms
memory: 8900kb
input:
27875
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0...
result:
ok 27875 numbers
Test #27:
score: 0
Accepted
time: 1203ms
memory: 9032kb
input:
29438
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0...
result:
ok 29438 numbers
Test #28:
score: 0
Accepted
time: 1213ms
memory: 8920kb
input:
29062
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0...
result:
ok 29062 numbers
Test #29:
score: 0
Accepted
time: 1207ms
memory: 9168kb
input:
29415
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0...
result:
ok 29415 numbers
Test #30:
score: 0
Accepted
time: 1210ms
memory: 9072kb
input:
29394
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0...
result:
ok 29394 numbers
Test #31:
score: 0
Accepted
time: 1185ms
memory: 9216kb
input:
29485
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0...
result:
ok 29485 numbers