QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#235370 | #667. Randomized Binary Search Tree | ckiseki# | AC ✓ | 231ms | 12304kb | C++20 | 3.0kb | 2023-11-02 18:11:19 | 2023-11-02 18:11:20 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#include <experimental/iterator>
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(const char *s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
void orange_(const char *s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
namespace {
using llf = double;
using C = complex<llf>;
const llf PI = acos(llf(-1));
template <int maxn>
struct FFT {
C roots[maxn];
FFT() {
for (int i = maxn >> 1; i; i >>= 1) {
for (int j = 0; j < i; ++j)
roots[i + j] = polar<llf>(1, PI * j / i);
}
}
void operator()(C F[], int n, bool inv = false) {
for (int i = 0, j = 0; i < n; ++i) {
if (i < j) swap(F[i], F[j]);
for (int k = n >> 1; (j ^= k) < k; k >>= 1);
}
for (int s = 1; s < n; s *= 2) {
for (int i = 0; i < n; i += s * 2) {
for (int j = 0; j < s; j++) {
C a = F[i + j], b = F[i + j + s] * roots[s + j];
F[i + j] = a + b;
F[i + j + s] = a - b;
}
}
}
if (inv) {
for (int i = 0; i < n; ++i)
F[i] /= n;
reverse(F + 1, F + n);
}
}
};
FFT<1 << 18> fft;
vector<llf> mul(vector<llf> a, vector<llf> b) {
int sz = 1;
while (sz < int(a.size() + b.size()))
sz *= 2;
vector<C> A(sz), B(sz);
for (size_t i = 0; i < a.size(); ++i)
A[i] = C{a[i], 0};
for (size_t i = 0; i < b.size(); ++i)
B[i] = C{b[i], 0};
fft(A.data(), sz);
fft(B.data(), sz);
for (int i = 0; i < sz; ++i)
A[i] *= B[i];
fft(A.data(), sz, true);
vector<llf> c(a.size() + b.size() - 1);
for (size_t i = 0; i < c.size(); ++i)
c[i] = real(A[i]);
//for (size_t i = 0; i < a.size(); i++)
// for (size_t j = 0; j < b.size(); j++)
// c[i + j] += a[i] * b[j];
return c;
}
vector<llf> integ(vector<llf> a) {
a.insert(a.begin(), 0);
for (size_t i = 1; i < a.size(); i++)
a[i] /= i;
return a;
}
} // namespace
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cout.precision(20);
cout << fixed;
int n; cin >> n;
vector<llf> g = {1};
//auto last = g;
//last[0] = 1;
//last[1] = 0;
for (int it = 0; it < n; it++) {
//orange(all(g));
if (it > 80)
{
cout << "0\n";
continue;
}
auto gg = g;
g = integ(mul(g, g));
g[0] += 1;
if (g.size() > 30001)
g.resize(30001);
auto v = g;
if (it == 0)
{
gg[0] = 0;
}
for (int i = 0; i < gg.size(); ++i)
v[i] -= gg[i];
orange(all(g));
orange(all(v));
if (g.size() > n) cout << v[n] << '\n';
else cout << "0" << '\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 7896kb
input:
1
output:
1.00000000000000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 5ms
memory: 8068kb
input:
2
output:
0 1.00000000000000000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 8064kb
input:
3
output:
0 0.33333333333333331483 0.66666666666666651864
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 6ms
memory: 7976kb
input:
4
output:
0 0 0.66666666666666651864 0.33333333333333325932
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 6ms
memory: 7964kb
input:
5
output:
0 0 0.33333333333333325932 0.53333333333333321491 0.13333333333333319271
result:
ok 5 numbers
Test #6:
score: 0
Accepted
time: 5ms
memory: 7976kb
input:
6
output:
0 0 0.11111111111111104943 0.55555555555555546920 0.28888888888888863971 0.04444444444444362041
result:
ok 6 numbers
Test #7:
score: 0
Accepted
time: 3ms
memory: 8080kb
input:
7
output:
0 0 0.01587301587301587907 0.44444444444444430875 0.40634920634920607130 0.12063492063492009532 0.01269841269841132103
result:
ok 7 numbers
Test #8:
score: 0
Accepted
time: 6ms
memory: 8016kb
input:
8
output:
0 0 0 0.28174603174603174427 0.46666666666666634100 0.20714285714285640694 0.04126984126984012402 0.00317460317460160901
result:
ok 8 numbers
Test #9:
score: 0
Accepted
time: 3ms
memory: 8108kb
input:
9
output:
0 0 0 0.15167548500881830598 0.46507936507936487036 0.28783068783068721519 0.08271604938271459595 0.01199294532627714904 0.00070546737213172950
result:
ok 9 numbers
Test #10:
score: 0
Accepted
time: 3ms
memory: 8144kb
input:
10
output:
0 0 0 0.06984126984126982907 0.41557319223985883516 0.35206349206349135672 0.13201058201058069042 0.02733686067019225341 0.00303350970017357557 0.00014109347442248232
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 208ms
memory: 12176kb
input:
30000
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.00000000000000000006 -0.00000000000000000002 0.00000000000000000028 -0.00000000000000000015 0.00000000000000000010 -0.00000000000000000019 -0.00000000000000000042 0.00000000000000000018 0.00000000000000000003 -0.00000000000000000283 0.00000000000000000383 -0.0000000000...
result:
ok 30000 numbers
Test #12:
score: 0
Accepted
time: 133ms
memory: 12112kb
input:
56
output:
0 0 0 0 0 0.00000000000000074544 0.00001005571821283289 0.00660281182019347140 0.09098155849589592559 0.24453503605629878237 0.28157059909569087663 0.20093514823312619288 0.10627731601666212669 0.04550174512118621006 0.01649757726914657940 0.00519314100284951063 0.00144092730091971433 0.000356009333...
result:
ok 56 numbers
Test #13:
score: 0
Accepted
time: 215ms
memory: 12156kb
input:
154
output:
0 0 0 0 0 0 0 -0.00000000000000001153 0.00000000018833079306 0.00001554381777536930 0.00314015014659804617 0.04496213442041847169 0.15814480517356035993 0.24545941703695389746 0.23169695454014227476 0.15926864898430781459 0.08825692922788075379 0.04176811195940721699 0.01745540201613771103 0.0065726...
result:
ok 154 numbers
Test #14:
score: 0
Accepted
time: 227ms
memory: 12168kb
input:
230
output:
0 0 0 0 0 0 0 -0.00000000000000001086 0.00000000000000000429 0.00000000000898870630 0.00000187186104500406 0.00081328109335230051 0.01986507472047740336 0.10225960707652508030 0.20879205059257843757 0.24087962933304818414 0.19301444207805962261 0.12120704421524042260 0.06402399834513472499 0.0296596...
result:
ok 230 numbers
Test #15:
score: 0
Accepted
time: 215ms
memory: 12124kb
input:
198
output:
0 0 0 0 0 0 0 -0.00000000000000000891 0.00000000000000003265 0.00000000782279327731 0.00005994658367346873 0.00537617606439282601 0.05505072727456675891 0.16646608730183715119 0.24198555781627531514 0.22307257692923604386 0.15299807331616410710 0.08562756792318504395 0.04125937829673465007 0.0176668...
result:
ok 198 numbers
Test #16:
score: 0
Accepted
time: 225ms
memory: 12120kb
input:
274
output:
0 0 0 0 0 0 0 0 0.00000000000000000000 0.00000000000000013724 0.00000000716181010576 0.00003970879034426985 0.00370438802927092409 0.04219404352872770797 0.14237962694849146117 0.22788577520506531071 0.22778524370367408958 0.16740361760938071711 0.09965647550981171499 0.05090343442214673164 0.023092...
result:
ok 274 numbers
Test #17:
score: 0
Accepted
time: 220ms
memory: 12232kb
input:
657
output:
0 0 0 0 0 0 0 0 0 0.00000000000000000105 -0.00000000000000000204 0.00000000000000000160 0.00000000000004648784 0.00000002490354022285 0.00003863339552175437 0.00264378216892168080 0.02985224566437543262 0.11031635690266190786 0.19873273889984197083 0.22362161331615404425 0.18367423410748973112 0.121...
result:
ok 657 numbers
Test #18:
score: 0
Accepted
time: 211ms
memory: 12124kb
input:
628
output:
0 0 0 0 0 0 0 0 0 -0.00000000000000000031 -0.00000000000000000093 0.00000000000000000484 0.00000000000057377877 0.00000010400635212997 0.00008953114309647901 0.00435205902221951109 0.03968698151572227356 0.12750125498677694624 0.20917986150261258516 0.22085379353290507387 0.17347872215763826542 0.11...
result:
ok 628 numbers
Test #19:
score: 0
Accepted
time: 212ms
memory: 12152kb
input:
1319
output:
0 0 0 0 0 0 0 0 0 0 0.00000000000000000054 0.00000000000000000198 -0.00000000000000000133 0.00000000000000000047 0.00000000000000008689 0.00000000029874192925 0.00000193677363683414 0.00036564929418054587 0.00848715010040175348 0.05286654930088705018 0.13937652590210813930 0.20739619959207611366 0.2...
result:
ok 1319 numbers
Test #20:
score: 0
Accepted
time: 201ms
memory: 12172kb
input:
1453
output:
0 0 0 0 0 0 0 0 0 0 0.00000000000000000039 -0.00000000000000000012 0.00000000000000000281 -0.00000000000000000203 0.00000000000000000223 0.00000000000445376758 0.00000015108648201816 0.00007624468766843061 0.00326397246350110855 0.03036206078755987817 0.10488488261695293191 0.18767301040566486403 0....
result:
ok 1453 numbers
Test #21:
score: 0
Accepted
time: 217ms
memory: 12124kb
input:
1095
output:
0 0 0 0 0 0 0 0 0 0 -0.00000000000000000162 0.00000000000000000017 0.00000000000000000437 -0.00000000000000000552 0.00000000000365217972 0.00000016787494420316 0.00009062096943336412 0.00383264810274374463 0.03436978469328540176 0.11387389357765785591 0.19587237284738626131 0.21753544458615203805 0....
result:
ok 1095 numbers
Test #22:
score: 0
Accepted
time: 231ms
memory: 12124kb
input:
15826
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 -0.00000000000000000051 0.00000000000000000047 0.00000000000000000011 0.00000000000000000027 -0.00000000000000000032 -0.00000000000000000020 0.00000000000000000078 -0.00000000000000000009 0.00000000000000000095 -0.00000000000000000341 0.00000000000000003547 0.00000000002450...
result:
ok 15826 numbers
Test #23:
score: 0
Accepted
time: 206ms
memory: 12188kb
input:
12332
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 -0.00000000000000000011 -0.00000000000000000020 0.00000000000000000056 0.00000000000000000008 -0.00000000000000000010 -0.00000000000000000011 0.00000000000000000181 -0.00000000000000000180 -0.00000000000000000081 0.00000000000000001889 0.00000000001559837298 0.0000001228350...
result:
ok 12332 numbers
Test #24:
score: 0
Accepted
time: 212ms
memory: 12300kb
input:
7285
output:
0 0 0 0 0 0 0 0 0 0 0 0 -0.00000000000000000097 0.00000000000000000096 -0.00000000000000000031 0.00000000000000000066 -0.00000000000000000014 0.00000000000000000047 0.00000000000000000006 0.00000000000000000195 0.00000000000000000946 0.00000000001595970187 0.00000014664852138858 0.000048781221315901...
result:
ok 7285 numbers
Test #25:
score: 0
Accepted
time: 231ms
memory: 12160kb
input:
7621
output:
0 0 0 0 0 0 0 0 0 0 0 0 -0.00000000000000000043 -0.00000000000000000003 0.00000000000000000078 -0.00000000000000000012 0.00000000000000000062 -0.00000000000000000083 0.00000000000000000051 0.00000000000000000157 0.00000000000000000142 0.00000000000214163215 0.00000004034113166085 0.00002122736306285...
result:
ok 7621 numbers
Test #26:
score: 0
Accepted
time: 213ms
memory: 12168kb
input:
27875
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.00000000000000000013 0.00000000000000000001 0.00000000000000000015 -0.00000000000000000002 0.00000000000000000025 -0.00000000000000000037 0.00000000000000000025 -0.00000000000000000041 -0.00000000000000000104 0.00000000000000000030 0.00000000000000000209 0.000000000000...
result:
ok 27875 numbers
Test #27:
score: 0
Accepted
time: 214ms
memory: 12304kb
input:
29438
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.00000000000000000006 0.00000000000000000011 -0.00000000000000000003 0.00000000000000000019 -0.00000000000000000002 0.00000000000000000000 -0.00000000000000000110 0.00000000000000000044 -0.00000000000000000048 -0.00000000000000000261 0.00000000000000000537 -0.0000000000...
result:
ok 29438 numbers
Test #28:
score: 0
Accepted
time: 229ms
memory: 12304kb
input:
29062
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.00000000000000000005 -0.00000000000000000011 0.00000000000000000000 0.00000000000000000006 -0.00000000000000000016 0.00000000000000000016 -0.00000000000000000032 -0.00000000000000000020 0.00000000000000000024 -0.00000000000000000315 0.00000000000000000564 -0.00000000000...
result:
ok 29062 numbers
Test #29:
score: 0
Accepted
time: 208ms
memory: 12200kb
input:
29415
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.00000000000000000008 0.00000000000000000005 0.00000000000000000003 0.00000000000000000014 -0.00000000000000000008 -0.00000000000000000049 0.00000000000000000068 -0.00000000000000000056 -0.00000000000000000022 -0.00000000000000000402 -0.00000000000000000026 0.0000000000...
result:
ok 29415 numbers
Test #30:
score: 0
Accepted
time: 201ms
memory: 12172kb
input:
29394
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.00000000000000000013 0.00000000000000000011 0.00000000000000000007 0.00000000000000000017 -0.00000000000000000005 0.00000000000000000002 -0.00000000000000000051 -0.00000000000000000098 0.00000000000000000089 -0.00000000000000000190 0.00000000000000000078 0.000000000000...
result:
ok 29394 numbers
Test #31:
score: 0
Accepted
time: 205ms
memory: 12304kb
input:
29485
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.00000000000000000014 0.00000000000000000017 -0.00000000000000000003 0.00000000000000000024 0.00000000000000000002 -0.00000000000000000032 -0.00000000000000000013 0.00000000000000000003 0.00000000000000000123 -0.00000000000000000575 0.00000000000000000548 -0.00000000000...
result:
ok 29485 numbers