QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#229283 | #7644. Good Splits | ucup-team052# | TL | 1417ms | 42628kb | C++14 | 1.6kb | 2023-10-28 15:39:37 | 2023-10-28 15:39:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int md;
inline int add(int x, int y) {
if (x + y >= md) return x + y - md;
return x + y;
}
inline int sub(int x, int y) {
if (x < y) return x - y + md;
return x - y;
}
struct FastMod {
unsigned long long b, m;
FastMod() {}
FastMod(unsigned long long b) : b(b), m((unsigned long long)((__uint128_t(1) << 64) / b)) {}
unsigned long long operator()(unsigned long long a) {
unsigned long long q = (unsigned long long)((__uint128_t(m) * a) >> 64);
unsigned long long r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= b ? r - b : r;
}
} M;
inline int mul(int x, int y) {
return M(1ull * x * y);
}
const int N = 205;
int dp[N * 2][N][N], ans[N], ret[N];
int n;
inline void upd(int &x, int y) {
x = add(x, y);
}
inline void dec(int &x, int y) {
x = sub(x, y);
}
int main() {
cin >> n >> md; M = FastMod(md);
dp[1][1][0] = 1;
for (int i = 2; i <= n * 2; i++) {
for (int j = 0; j <= min(n, i); j++) {
for (int k = 0; k <= min(n, i) - j; k++) {
upd(dp[i][j][k], dp[i - 1][j + 1][k]);
upd(dp[i][j][k], dp[i - 1][j][k + 1]);
if (j) upd(dp[i][j][k], dp[i - 1][j - 1][k]);
if (k) upd(dp[i][j][k], dp[i - 1][j][k - 1]);
for (int t = 1; t <= i / 2; t++) {
dec(dp[i][j][k], mul(dp[i - t * 2][j][k], ret[t]));
}
}
}
if (i % 2 == 0) {
ret[i / 2] = dp[i][0][0];
dp[i][0][0] = 0;
}
}
ans[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) upd(ans[i], mul(ans[j], ret[i - j]));
cout << ans[i] << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3680kb
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: 1ms
memory: 4452kb
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: 2ms
memory: 4920kb
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: 12ms
memory: 7152kb
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: 155ms
memory: 16412kb
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: 735ms
memory: 31864kb
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: 1417ms
memory: 42628kb
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: 3608kb
input:
1 998244353
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: -100
Time Limit Exceeded
input:
200 864048671