QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232005#7644. Good Splitshos_lyricAC ✓28ms4536kbC++146.3kb2023-10-29 18:54:102023-10-29 18:54:10

Judging History

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

  • [2023-10-29 18:54:10]
  • 评测
  • 测评结果:AC
  • 用时:28ms
  • 内存:4536kb
  • [2023-10-29 18:54:10]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
// Barrett
struct ModInt {
  static unsigned M;
  static unsigned long long NEG_INV_M;
  static void setM(unsigned m) { M = m; NEG_INV_M = -1ULL / M; }
  unsigned x;
  ModInt() : x(0U) {}
  ModInt(unsigned x_) : x(x_ % M) {}
  ModInt(unsigned long long x_) : x(x_ % M) {}
  ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) {
    const unsigned long long y = static_cast<unsigned long long>(x) * a.x;
    const unsigned long long q = static_cast<unsigned long long>((static_cast<unsigned __int128>(NEG_INV_M) * y) >> 64);
    const unsigned long long r = y - M * q;
    x = r - M * (r >= M);
    return *this;
  }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
unsigned ModInt::M;
unsigned long long ModInt::NEG_INV_M;
// !!!Use ModInt::setM!!!
////////////////////////////////////////////////////////////////////////////////

using Mint = ModInt;

constexpr int LIM_INV = 1010;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];

void prepare() {
  inv[1] = 1;
  for (int i = 2; i < LIM_INV; ++i) {
    inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
  }
  fac[0] = invFac[0] = 1;
  for (int i = 1; i < LIM_INV; ++i) {
    fac[i] = fac[i - 1] * i;
    invFac[i] = invFac[i - 1] * inv[i];
  }
}
Mint binom(Int n, Int k) {
  if (n < 0) {
    if (k >= 0) {
      return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);
    } else if (n - k >= 0) {
      return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);
    } else {
      return 0;
    }
  } else {
    if (0 <= k && k <= n) {
      assert(n < LIM_INV);
      return fac[n] * invFac[k] * invFac[n - k];
    } else {
      return 0;
    }
  }
}


Mint cata(int n) {
  return inv[n + 1] * binom(2 * n, n);
}

int main() {
  int N, P;
  for (; ~scanf("%d%d", &N, &P); ) {
    Mint::setM(P);
    prepare();
    
    vector<Mint> fs(N + 1, 0);
    vector<vector<Mint>> ff(2 * N + 1, vector<Mint>(N + 1, 0));
    for (int n = 0; n <= N; ++n) {
      for (int i = 0; i <= n; ++i) {
        fs[n] += binom(2 * n, 2 * i) * cata(i) * cata(n - i);
      }
    }
// cerr<<"fs = "<<fs<<endl;
    ff[0][0] = 1;
    for (int k = 1; k <= 2 * N; ++k) {
      for (int n = 0; n <= N; ++n) {
        for (int i = 0; i <= n; ++i) {
          ff[k][n] += ff[k - 1][n - i] * fs[i];
        }
      }
    }
    
    auto cs = fs;
    cs[0] = 0;
    for (int k = 1; k <= N; ++k) {
      for (int i = 1; i <= N - k; ++i) {
        cs[k + i] -= cs[k] * ff[2 * k][i];
      }
    }
// cerr<<"cs = "<<cs<<endl;
    for (int n = 0; n <= N; ++n) {
      cs[n] /= 2;
    }
    
    vector<Mint> gs(N + 1, 0);
    vector<vector<Mint>> gg(2 * N + 1, vector<Mint>(N + 1, 0));
    gs[0] = 1;
    for (int k = 0; k <= 2 * N; ++k) {
      gg[k][0] = 1;
    }
    for (int n = 1; n <= N; ++n) {
      for (int k = 1; k <= n; ++k) {
        gs[n] += cs[k] * gg[2 * k][n - k];
      }
      for (int k = 1; k <= 2 * N; ++k) {
        for (int i = 0; i <= n; ++i) {
          gg[k][n] += gg[k - 1][n - i] * gs[i];
        }
      }
    }
// cerr<<"gs = "<<gs<<endl;
    
    for (int n = 1; n <= N; ++n) {
      printf("%u\n", gs[n].x);
    }
  }
  return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3780kb

input:

5 998244353

output:

1
3
14
84
592

result:

ok 5 number(s): "1 3 14 84 592"

Test #2:

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

input:

20 998244353

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
337584612
503820623
71483496
12733593
474907036
203223726
565209211
487441118
992424798
625482036

result:

ok 20 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

30 147084737

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
43415138
115604731
88255570
6762644
25928144
117374310
119291296
29414136
87790057
136053957
103827626
145662835
60977924
8837626
61475022
108138661
88536961
105609125
140429327
77714436

result:

ok 30 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

50 259851877

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
77732735
120479281
107558023
219154876
82657644
224090144
253190966
148874121
53920249
82785846
244357960
88406017
106161945
35184035
131007270
222579610
212725099
114435754
64242919
39323449
211238313
156440547
84150382
242052946
50634162
120017303
2...

result:

ok 50 numbers

Test #5:

score: 0
Accepted
time: 5ms
memory: 3948kb

input:

100 175127923

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
162456689
171123145
54532804
71333538
68283136
25628469
138841774
142350839
27676343
15931022
158187457
43201304
18465009
37939972
169592319
94983552
152752931
69017296
46403905
173424585
170947507
7870926
90491276
10182721
58907963
136216980
28163587...

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 12ms
memory: 4160kb

input:

150 367542041

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
337584612
190675313
252320457
264200037
124276323
161424010
184935571
230223063
343780965
314302578
342350468
265272499
173792750
339843799
301192856
263531782
208259173
113525686
44197147
288967350
139023077
142942582
324678736
318907769
315638511
40...

result:

ok 150 numbers

Test #7:

score: 0
Accepted
time: 20ms
memory: 4536kb

input:

177 861641813

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
337584612
51986430
817568411
233712834
530886113
262319436
602763301
391560421
714952237
234059952
504165773
214901044
343336951
654631331
578657419
506328910
26764748
407306588
36662800
819329882
372916107
103054885
512356475
207029843
192047130
1038...

result:

ok 177 numbers

Test #8:

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

input:

1 998244353

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 28ms
memory: 4524kb

input:

200 864048671

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
337584612
42358998
716480375
849841780
472934607
500922480
184767796
279937457
399183954
512063087
91797677
107549673
485929841
293677006
593203756
235501697
372544850
500179291
849823101
602694217
345293985
459931747
386664093
196167251
265892579
252...

result:

ok 200 numbers

Test #10:

score: 0
Accepted
time: 24ms
memory: 4460kb

input:

199 958494587

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
337584612
623069921
583730251
536976835
256616783
340763703
344818742
765288755
200573977
666742925
957661404
606909377
32714935
246057767
23198149
389527637
588746573
223336510
430768410
501175382
380964997
647932740
845833201
113681916
396614824
546...

result:

ok 199 numbers

Test #11:

score: 0
Accepted
time: 27ms
memory: 4456kb

input:

198 165619889

output:

1
3
14
84
592
4659
39699
359004
3399164
33378417
6344834
20536013
73289310
162017284
159458288
100856961
164827673
70631917
154742952
14393421
27830529
37917167
68934527
54693629
76175385
34254720
114820104
69340313
35844068
25551171
137354127
120937326
10672731
81957539
132401938
29387190
74534300
...

result:

ok 198 numbers

Extra Test:

score: 0
Extra Test Passed