QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#235375#667. Randomized Binary Search Tree8BQube#AC ✓150ms6436kbC++202.7kb2023-11-02 18:23:322023-11-02 18:23:33

Judging History

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

  • [2023-11-02 18:23:33]
  • 评测
  • 测评结果:AC
  • 用时:150ms
  • 内存:6436kb
  • [2023-11-02 18:23:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define SZ(a) ((int)a.size())

const int C = 60;
using val_t = complex<double>;

template<int MAXN>
struct FFT {
    const double PI = acos(-1);
    val_t w[MAXN];
    FFT() {
        for (int i = 0; i < MAXN; ++i) {
            double arg = 2 * PI * i / MAXN;
            w[i] = val_t(cos(arg), sin(arg));
        }
    }
    void bitrev(val_t *a, int n) {
        int i = 0;
        for (int j = 1; j < n - 1; ++j) {
            for (int k = n >> 1; (i ^= k) < k; k >>= 1);
            if (j < i) swap(a[i], a[j]);
        }
    }
    void operator()(val_t *a, int n, bool inv = false) {
        bitrev(a, n);
        for (int L = 2; L <= n; L <<= 1) {
            int dx = MAXN / L, dl = L >> 1;
            for (int i = 0; i < n; i += L) {
                for (int j = i, x = 0; j < i + dl; ++j, x += dx) {
                    val_t tmp = a[j + dl] * w[x];
                    a[j + dl] = a[j] - tmp;
                    a[j] += tmp;
                }
            }
        }
        if (inv) {
            reverse(a + 1, a + n);
            for (int i = 0; i < n; ++i) a[i] /= n;
        }
    }
};

const int N = 1 << 16;

#define fi(s, n) for (int i = (int)(s); i < (int)(n); ++i)
template<int MAXN>
struct Poly : vector<val_t> {
    using vector<val_t>::vector;
    static FFT<MAXN> fft;
    int n() const { return (int)size(); }
    Poly(const Poly &p, int m): vector<val_t>(m) {
        copy_n(p.data(), min(p.n(), m), data());
    }
    Poly &isz(int m) { return resize(m), *this; }
    Poly Mul(const Poly &rhs) const {
        int m = 1;
        while (m < n() + rhs.n() - 1) m <<= 1;
        Poly X(*this, m), Y(rhs, m);
        fft(X.data(), m), fft(Y.data(), m);
        fi(0, m) X[i] = X[i] * Y[i];
        fft(X.data(), m, true);
        return X.isz(n() + rhs.n() - 1);
    }
};
#undef fi
using Poly_t = Poly<N>;
template<> decltype(Poly_t::fft) Poly_t::fft = {};

FFT<N> fft;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;

    vector<val_t> dp(N);
    dp[0] = 1;
    cout << fixed << setprecision(8);
    double last = 0;
    for (int i = 1; i <= n && i < C; ++i) {
        fft(dp.data(), N);
        for (int j = 0; j < N; ++j)
            dp[j] *= dp[j];
        fft(dp.data(), N, true);
        for (int j = n + 1; j < N; ++j)
            dp[j] = 0;
        for (int j = n; j >= 1; --j) {
            dp[j] = val_t(dp[j - 1].real() / (double)j, 0);
        }
        dp[0] = 1;
        cout << (dp[n].real() - last) << "\n";
        last = dp[n].real();
    }
    for (int i = C; i <= n; ++i)
        cout << (double)0 << "\n";
}

详细

Test #1:

score: 100
Accepted
time: 6ms
memory: 6360kb

input:

1

output:

1.00000000

result:

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

Test #2:

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

input:

2

output:

0.00000000
1.00000000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 11ms
memory: 6364kb

input:

3

output:

0.00000000
0.33333333
0.66666667

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 9ms
memory: 6360kb

input:

4

output:

0.00000000
0.00000000
0.66666667
0.33333333

result:

ok 4 numbers

Test #5:

score: 0
Accepted
time: 16ms
memory: 6436kb

input:

5

output:

0.00000000
0.00000000
0.33333333
0.53333333
0.13333333

result:

ok 5 numbers

Test #6:

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

input:

6

output:

0.00000000
0.00000000
0.11111111
0.55555556
0.28888889
0.04444444

result:

ok 6 numbers

Test #7:

score: 0
Accepted
time: 21ms
memory: 6360kb

input:

7

output:

0.00000000
0.00000000
0.01587302
0.44444444
0.40634921
0.12063492
0.01269841

result:

ok 7 numbers

Test #8:

score: 0
Accepted
time: 23ms
memory: 6388kb

input:

8

output:

0.00000000
0.00000000
0.00000000
0.28174603
0.46666667
0.20714286
0.04126984
0.00317460

result:

ok 8 numbers

Test #9:

score: 0
Accepted
time: 25ms
memory: 6364kb

input:

9

output:

0.00000000
0.00000000
0.00000000
0.15167549
0.46507937
0.28783069
0.08271605
0.01199295
0.00070547

result:

ok 9 numbers

Test #10:

score: 0
Accepted
time: 23ms
memory: 6372kb

input:

10

output:

0.00000000
0.00000000
0.00000000
0.06984127
0.41557319
0.35206349
0.13201058
0.02733686
0.00303351
0.00014109

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 150ms
memory: 6320kb

input:

30000

output:

0.00000000
-0.00000000
-0.00000000
-0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.000000...

result:

ok 30000 numbers

Test #12:

score: 0
Accepted
time: 130ms
memory: 6372kb

input:

56

output:

0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00001006
0.00660281
0.09098156
0.24453504
0.28157060
0.20093515
0.10627732
0.04550175
0.01649758
0.00519314
0.00144093
0.00035601
0.00007890
0.00001577
0.00000286
0.00000047
0.00000007
0.00000001
0.00000000
0.00000000
0.00000000
0.0...

result:

ok 56 numbers

Test #13:

score: 0
Accepted
time: 139ms
memory: 6360kb

input:

154

output:

0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00001554
0.00314015
0.04496213
0.15814481
0.24545942
0.23169695
0.15926865
0.08825693
0.04176811
0.01745540
0.00657267
0.00225872
0.00071467
0.00020954
0.00005721
0.00001460
0.00000350
0.00000079
0.0...

result:

ok 154 numbers

Test #14:

score: 0
Accepted
time: 139ms
memory: 6364kb

input:

230

output:

0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000187
0.00081328
0.01986507
0.10225961
0.20879205
0.24087963
0.19301444
0.12120704
0.06402400
0.02965968
0.01235717
0.00470367
0.00165287
0.00054013
0.00016504
0.00004735
0.00001280
0....

result:

ok 230 numbers

Test #15:

score: 0
Accepted
time: 138ms
memory: 6408kb

input:

198

output:

0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000001
0.00005995
0.00537618
0.05505073
0.16646609
0.24198556
0.22307258
0.15299807
0.08562757
0.04125938
0.01766681
0.00685348
0.00243882
0.00080290
0.00024606
0.00007054
0.00001898
0.00000481
0.0...

result:

ok 198 numbers

Test #16:

score: 0
Accepted
time: 139ms
memory: 6408kb

input:

274

output:

0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000001
0.00003971
0.00370439
0.04219404
0.14237963
0.22788578
0.22778524
0.16740362
0.09965648
0.05090343
0.02309276
0.00950357
0.00359628
0.00126281
0.00041416
0.00012749
0.00003698
0....

result:

ok 274 numbers

Test #17:

score: 0
Accepted
time: 140ms
memory: 6320kb

input:

657

output:

0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000002
0.00003863
0.00264378
0.02985225
0.11031636
0.19873274
0.22362161
0.18367423
0.12141609
0.06865469
0.03449497
0.01577371
0.00666633
0.00263061...

result:

ok 657 numbers

Test #18:

score: 0
Accepted
time: 135ms
memory: 6364kb

input:

628

output:

0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000010
0.00008953
0.00435206
0.03968698
0.12750125
0.20917986
0.22085379
0.17347872
0.11099083
0.06119690
0.03011972
0.01352939
0.00562629
0.00218695...

result:

ok 628 numbers

Test #19:

score: 0
Accepted
time: 140ms
memory: 6388kb

input:

1319

output:

0.00000000
0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000194
0.00036565
0.00848715
0.05286655
0.13937653
0.20739620
0.20993877
0.16314815
0.10521768
0.05919518
0.02999516
...

result:

ok 1319 numbers

Test #20:

score: 0
Accepted
time: 136ms
memory: 6296kb

input:

1453

output:

0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000015
0.00007624
0.00326397
0.03036206
0.10488488
0.18767301
0.21582450
0.18357961
0.12649831
0.07487279
0.03952523...

result:

ok 1453 numbers

Test #21:

score: 0
Accepted
time: 138ms
memory: 6360kb

input:

1095

output:

0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000017
0.00009062
0.00383265
0.03436978
0.11387389
0.19587237
0.21753544
0.17950258
0.12040819
0.06953194
0.03585063
0.01689363...

result:

ok 1095 numbers

Test #22:

score: 0
Accepted
time: 142ms
memory: 6408kb

input:

15826

output:

0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
-0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000015
0....

result:

ok 15826 numbers

Test #23:

score: 0
Accepted
time: 136ms
memory: 6224kb

input:

12332

output:

0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000012
0.00003975
0.0016...

result:

ok 12332 numbers

Test #24:

score: 0
Accepted
time: 138ms
memory: 6400kb

input:

7285

output:

0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000015
0.00004878
0.00195897
0.01958140
0.0762...

result:

ok 7285 numbers

Test #25:

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

input:

7621

output:

0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000004
0.00002123
0.00115080
0.01409084
0.0631...

result:

ok 7621 numbers

Test #26:

score: 0
Accepted
time: 143ms
memory: 6364kb

input:

27875

output:

0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
0....

result:

ok 27875 numbers

Test #27:

score: 0
Accepted
time: 147ms
memory: 6404kb

input:

29438

output:

0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
0...

result:

ok 29438 numbers

Test #28:

score: 0
Accepted
time: 144ms
memory: 6316kb

input:

29062

output:

0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0...

result:

ok 29062 numbers

Test #29:

score: 0
Accepted
time: 142ms
memory: 6368kb

input:

29415

output:

0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0....

result:

ok 29415 numbers

Test #30:

score: 0
Accepted
time: 148ms
memory: 6316kb

input:

29394

output:

0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
-0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
-0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
...

result:

ok 29394 numbers

Test #31:

score: 0
Accepted
time: 145ms
memory: 6364kb

input:

29485

output:

0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
0.00000000
-0.00000000
-0.00000000
0.00000000
0....

result:

ok 29485 numbers