QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#229275 | #7644. Good Splits | ucup-team052# | TL | 1106ms | 31640kb | C++14 | 1.2kb | 2023-10-28 15:38:16 | 2023-10-28 15:38:16 |
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;
}
inline int mul(int x, int y) {
return 1ull * x * y % md;
}
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;
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: 3484kb
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: 4176kb
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: 4ms
memory: 4688kb
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: 11ms
memory: 6772kb
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: 188ms
memory: 16248kb
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: 1106ms
memory: 31640kb
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: -100
Time Limit Exceeded
input:
177 861641813