QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#852566#667. Randomized Binary Search TreeliyujiaAC ✓1224ms9216kbC++145.2kb2025-01-11 12:49:062025-01-11 12:49:08

Judging History

This is the latest submission verdict.

  • [2025-01-11 12:49:08]
  • Judged
  • Verdict: AC
  • Time: 1224ms
  • Memory: 9216kb
  • [2025-01-11 12:49:06]
  • Submitted

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