QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#498901#667. Randomized Binary Search TreemshcherbaAC ✓333ms8160kbC++203.1kb2024-07-30 21:16:462024-07-30 21:16:46

Judging History

你现在查看的是最新测评结果

  • [2024-07-30 21:16:46]
  • 评测
  • 测评结果:AC
  • 用时:333ms
  • 内存:8160kb
  • [2024-07-30 21:16:46]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

typedef complex<db> com;

const db PI = acos(-1.0);
const int LEN = 1 << 16;

com pw[LEN];

void initFFT()
{
	db angle = 2 * PI / LEN;
	FOR(i, 0, LEN)
		pw[i] = {cos(i * angle), sin(i * angle)};
}

void fft(vector<com>& a, bool inv)
{
	int lg = __builtin_ctz(SZ(a));
	FOR(i, 0, SZ(a))
	{
		int k = 0;
		FOR(j, 0, lg)
			k |= ((i >> j) & 1) << (lg - j - 1);
		if(i < k)
			swap(a[i], a[k]);
	}
	int k = inv ? LEN - LEN / 4 : LEN / 4;
	//int g = inv ? binpow(GEN, mod - 2) : GEN, k = binpow(g, LEN / 4);
	for(int len = 1; len < SZ(a); len *= 4)
	{
		if (2 * len == SZ(a))
		{
			int diff = inv ? LEN - LEN / (2 * len) : LEN / (2 * len), pos = 0;
			// int ml = binpow(g, LEN / (2 * len)), pw = 1;
			FOR(j, 0, len)
			{
				com u = a[j];
				com v = a[j + len] * pw[pos];
				a[j] = u + v;
				a[j + len] = u - v;
				pos = (pos + diff) % LEN;
				// pw = mult(pw, ml);
			}
		}
		else
		{
			int diff = inv ? LEN - LEN / (4 * len) : LEN / (4 * len), pos = 0;
			// int ml = binpow(g, LEN / (4 * len)), pw = 1;
			FOR(j, 0, len)
			{
				int pos2 = (2 * pos) % LEN, pos3 = (3 * pos) % LEN;
				// int pw2 = mult(pw, pw), pw3 = mult(pw2, pw);
				for(int i = j; i < SZ(a); i += 4 * len)
				{
					com a0 = a[i];
					com a1 = a[i + len] * pw[pos2];
					com a2 = a[i + 2 * len] * pw[pos];
					com a3 = a[i + 3 * len] * pw[pos3];
					com a0p1 = a0 + a1, a2p3 = a2 + a3,
						a0m1 = a0 - a1, a2m3 = pw[k] * (a2 - a3); // pw[k] * 
					a[i] = a0p1 + a2p3;
					a[i + len] = a0m1 + a2m3;
					a[i + 2 * len] = a0p1 - a2p3;
					a[i + 3 * len] = a0m1 - a2m3;
				}
				pos = (pos + diff) % LEN;
				//pw = mult(pw, ml);
			}
		}
	}
	if(inv)
	{
		// int m = binpow(SZ(a), mod - 2);
		FOR(i, 0, SZ(a))
			a[i] /= SZ(a);
			// a[i] = mult(a[i], m); 
	}
}

vector<db> mult(const vector<db>& a, const vector<db>& b)
{
	vector<com> ac(ALL(a)), bc(ALL(b));
	int lg = 0;
	while ((1 << lg) < SZ(a) + SZ(b) - 1)
		lg++;
	ac.resize(1 << lg);
	bc.resize(1 << lg);
	fft(ac, false);
	fft(bc, false);
	FOR(i, 0, SZ(ac))
		ac[i] *= bc[i];
	fft(ac, true);
	vector<db> c(SZ(a) + SZ(b) - 1);
	FOR(i, 0, SZ(c))
		c[i] = ac[i].real();
	return c;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(6);
	initFFT();
	int n;
	cin >> n;
	vector<db> ans(n, 1);
	if (n > 1)
		ans[0] = 0;
	vector<db> f = {1, 1};
	FOR(j, 1, min(n, 55))
	{
		vector<db> nf = mult(f, f);
		f.resize(min(n, SZ(nf)) + 1);
		f[0] = 1;
		FOR(i, 1, SZ(f))
			f[i] = nf[i - 1] / i;
		ans[j] = n < SZ(f) ? f[n] : 0;
	}
	RFOR(i, SZ(ans), 1)
		ans[i] -= ans[i - 1];
	FOR(i, 0, n)
		cout << ans[i] << "\n";
	cerr << (db)clock() / CLOCKS_PER_SEC << endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 5156kb

input:

1

output:

1.000000

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 5092kb

input:

2

output:

0.000000
1.000000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 5140kb

input:

3

output:

0.000000
0.333333
0.666667

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 5228kb

input:

4

output:

0.000000
0.000000
0.666667
0.333333

result:

ok 4 numbers

Test #5:

score: 0
Accepted
time: 2ms
memory: 5128kb

input:

5

output:

0.000000
0.000000
0.333333
0.533333
0.133333

result:

ok 5 numbers

Test #6:

score: 0
Accepted
time: 2ms
memory: 5092kb

input:

6

output:

0.000000
0.000000
0.111111
0.555556
0.288889
0.044444

result:

ok 6 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 5240kb

input:

7

output:

0.000000
0.000000
0.015873
0.444444
0.406349
0.120635
0.012698

result:

ok 7 numbers

Test #8:

score: 0
Accepted
time: 2ms
memory: 5244kb

input:

8

output:

0.000000
0.000000
0.000000
0.281746
0.466667
0.207143
0.041270
0.003175

result:

ok 8 numbers

Test #9:

score: 0
Accepted
time: 2ms
memory: 5104kb

input:

9

output:

0.000000
0.000000
0.000000
0.151675
0.465079
0.287831
0.082716
0.011993
0.000705

result:

ok 9 numbers

Test #10:

score: 0
Accepted
time: 2ms
memory: 5124kb

input:

10

output:

0.000000
0.000000
0.000000
0.069841
0.415573
0.352063
0.132011
0.027337
0.003034
0.000141

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 333ms
memory: 8160kb

input:

30000

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
-0.000000
-0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000003
0.000302
0.005594
0.034717
0.100...

result:

ok 30000 numbers

Test #12:

score: 0
Accepted
time: 2ms
memory: 5264kb

input:

56

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000010
0.006603
0.090982
0.244535
0.281571
0.200935
0.106277
0.045502
0.016498
0.005193
0.001441
0.000356
0.000079
0.000016
0.000003
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
-0.000000
-0.000000...

result:

ok 56 numbers

Test #13:

score: 0
Accepted
time: 3ms
memory: 5260kb

input:

154

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000016
0.003140
0.044962
0.158145
0.245459
0.231697
0.159269
0.088257
0.041768
0.017455
0.006573
0.002259
0.000715
0.000210
0.000057
0.000015
0.000003
0.000001
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.0...

result:

ok 154 numbers

Test #14:

score: 0
Accepted
time: 3ms
memory: 5332kb

input:

230

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000002
0.000813
0.019865
0.102260
0.208792
0.240880
0.193014
0.121207
0.064024
0.029660
0.012357
0.004704
0.001653
0.000540
0.000165
0.000047
0.000013
0.000003
0.000001
0.000000
0.000000
0.000000
0.000000
0....

result:

ok 230 numbers

Test #15:

score: 0
Accepted
time: 0ms
memory: 5332kb

input:

198

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000060
0.005376
0.055051
0.166466
0.241986
0.223073
0.152998
0.085628
0.041259
0.017667
0.006853
0.002439
0.000803
0.000246
0.000071
0.000019
0.000005
0.000001
0.000000
0.000000
0.000000
0.000000
0.000000
0.0...

result:

ok 198 numbers

Test #16:

score: 0
Accepted
time: 2ms
memory: 5332kb

input:

274

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000040
0.003704
0.042194
0.142380
0.227886
0.227785
0.167404
0.099656
0.050903
0.023093
0.009504
0.003596
0.001263
0.000414
0.000127
0.000037
0.000010
0.000003
0.000001
0.000000
0.000000
0.000000
0....

result:

ok 274 numbers

Test #17:

score: 0
Accepted
time: 8ms
memory: 5276kb

input:

657

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
-0.000000
0.000000
0.000000
0.000039
0.002644
0.029852
0.110316
0.198733
0.223622
0.183674
0.121416
0.068655
0.034495
0.015774
0.006666
0.002631
0.000976
0.000342
0.000114
0.000036
0.000011
0.000003
...

result:

ok 657 numbers

Test #18:

score: 0
Accepted
time: 8ms
memory: 5408kb

input:

628

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
0.000000
0.000090
0.004352
0.039687
0.127501
0.209180
0.220854
0.173479
0.110991
0.061197
0.030120
0.013529
0.005626
0.002187
0.000800
0.000277
0.000091
0.000028
0.000008
0.000002
0...

result:

ok 628 numbers

Test #19:

score: 0
Accepted
time: 17ms
memory: 5376kb

input:

1319

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000002
0.000366
0.008487
0.052867
0.139377
0.207396
0.209939
0.163148
0.105218
0.059195
0.029995
0.013974
0.006067
0.002477
0.000957
0.000352
0.000123
0...

result:

ok 1319 numbers

Test #20:

score: 0
Accepted
time: 18ms
memory: 5252kb

input:

1453

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
0.000076
0.003264
0.030362
0.104885
0.187673
0.215824
0.183580
0.126498
0.074873
0.039525
0.019066
0.008537
0.003586
0.001423
0.000537
0.000193
0...

result:

ok 1453 numbers

Test #21:

score: 0
Accepted
time: 17ms
memory: 5412kb

input:

1095

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000091
0.003833
0.034370
0.113874
0.195872
0.217535
0.179503
0.120408
0.069532
0.035851
0.016894
0.007387
0.003027
0.001171
0.000430
0.000150
0.000050
0.0...

result:

ok 1095 numbers

Test #22:

score: 0
Accepted
time: 151ms
memory: 6340kb

input:

15826

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
-0.000000
-0.000000
-0.000000
-0.000000
-0.000000
0.000000
-0.000000
-0.000000
0.000000
0.000000
0.000000
0.000044
0.001711
0.017234
0.069000
0.145474
0.196004
0.19...

result:

ok 15826 numbers

Test #23:

score: 0
Accepted
time: 137ms
memory: 5980kb

input:

12332

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
0.000000
0.000040
0.001632
0.016961
0.068941
0.146221
0.197180
0.193626
0.151883...

result:

ok 12332 numbers

Test #24:

score: 0
Accepted
time: 65ms
memory: 5680kb

input:

7285

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
0.000000
0.000049
0.001959
0.019581
0.076265
0.155347
0.202072
0.192289
0.146731
0.095490
0.055219...

result:

ok 7285 numbers

Test #25:

score: 0
Accepted
time: 73ms
memory: 5708kb

input:

7621

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
-0.000000
0.000000
-0.000000
0.000000
-0.000000
-0.000000
0.000000
0.000000
0.000021
0.001151
0.014091
0.063148
0.141854
0.197634
0.197443
0.156049
0.104233
0.0614...

result:

ok 7621 numbers

Test #26:

score: 0
Accepted
time: 294ms
memory: 8084kb

input:

27875

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
0.000015
0.000814
0.010537
0.050877
0.12342...

result:

ok 27875 numbers

Test #27:

score: 0
Accepted
time: 316ms
memory: 8160kb

input:

29438

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000005
0.000394
0.006640
0.038533
0.10641...

result:

ok 29438 numbers

Test #28:

score: 0
Accepted
time: 333ms
memory: 7996kb

input:

29062

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
-0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
0.000007
0.000471
0.007435
0.041266
0.110...

result:

ok 29062 numbers

Test #29:

score: 0
Accepted
time: 331ms
memory: 8144kb

input:

29415

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
0.000000
0.000000
0.000000
0.000005
0.000399
0.006686
0.038696
0.10666...

result:

ok 29415 numbers

Test #30:

score: 0
Accepted
time: 308ms
memory: 7948kb

input:

29394

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
0.000005
0.000403
0.006729
0.038846
0.106883...

result:

ok 29394 numbers

Test #31:

score: 0
Accepted
time: 305ms
memory: 8128kb

input:

29485

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
-0.000000
0.000000
-0.000000
0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000005
0.000386
0.006546
0.038202
0.1059...

result:

ok 29485 numbers