QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#235364#667. Randomized Binary Search Treeckiseki#TL 894ms20988kbC++202.9kb2023-11-02 18:07:562023-11-02 18:07:58

Judging History

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

  • [2023-11-02 18:07:58]
  • 评测
  • 测评结果:TL
  • 用时:894ms
  • 内存:20988kb
  • [2023-11-02 18:07:56]
  • 提交

answer

#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

using llf = long 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;
}

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 * n > 1500000)
    {
      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: 14ms
memory: 11712kb

input:

1

output:

1.00000000000000000000

result:

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

Test #2:

score: 0
Accepted
time: 14ms
memory: 11784kb

input:

2

output:

0
1.00000000000000000000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 14ms
memory: 11960kb

input:

3

output:

0
0.33333333333333333334
0.66666666666666666663

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 14ms
memory: 11824kb

input:

4

output:

0
0
0.66666666666666666668
0.33333333333333333353

result:

ok 4 numbers

Test #5:

score: 0
Accepted
time: 14ms
memory: 11960kb

input:

5

output:

0
0
0.33333333333333333332
0.53333333333333333347
0.13333333333333333354

result:

ok 5 numbers

Test #6:

score: 0
Accepted
time: 10ms
memory: 11876kb

input:

6

output:

0
0
0.11111111111111111113
0.55555555555555555567
0.28888888888888888907
0.04444444444444444468

result:

ok 6 numbers

Test #7:

score: 0
Accepted
time: 10ms
memory: 11928kb

input:

7

output:

0
0
0.01587301587301587302
0.44444444444444444447
0.40634920634920634945
0.12063492063492063525
0.01269841269841269867

result:

ok 7 numbers

Test #8:

score: 0
Accepted
time: 14ms
memory: 11864kb

input:

8

output:

0
0
0
0.28174603174603174606
0.46666666666666666686
0.20714285714285714322
0.04126984126984127018
0.00317460317460317487

result:

ok 8 numbers

Test #9:

score: 0
Accepted
time: 14ms
memory: 11900kb

input:

9

output:

0
0
0
0.15167548500881834215
0.46507936507936507956
0.28783068783068783102
0.08271604938271604976
0.01199294532627866010
0.00070546737213403928

result:

ok 9 numbers

Test #10:

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

input:

10

output:

0
0
0
0.06984126984126984128
0.41557319223985890661
0.35206349206349206395
0.13201058201058201103
0.02733686067019400385
0.00303350970017636750
0.00014109347442680905

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 809ms
memory: 20840kb

input:

30000

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0.00000000000000000000
-0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
-0.00000000000000000000
-0.00000000000000000000
0.00000000000000000000
-0.00000000000000000000
-0.00000000000000000000
0.00000000000000000000
0.000000000000...

result:

ok 30000 numbers

Test #12:

score: 0
Accepted
time: 894ms
memory: 20988kb

input:

56

output:

0
0
0
0
0
0.00000000000000077985
0.00001005571821279373
0.00660281182019344961
0.09098155849589653121
0.24453503605630293722
0.28157059909570150187
0.20093514823314507790
0.10627731601669013358
0.04550174512122505925
0.01649757726919998200
0.00519314100292211711
0.00144092730101848260
0.000356009333...

result:

ok 56 numbers

Test #13:

score: -100
Time Limit Exceeded

input:

154

output:


result: