QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#235370#667. Randomized Binary Search Treeckiseki#AC ✓231ms12304kbC++203.0kb2023-11-02 18:11:192023-11-02 18:11:20

Judging History

This is the latest submission verdict.

  • [2023-11-02 18:11:20]
  • Judged
  • Verdict: AC
  • Time: 231ms
  • Memory: 12304kb
  • [2023-11-02 18:11:19]
  • Submitted

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