QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#583756 | #8820. Exchanging Kubic 2 | hhoppitree | TL | 2ms | 10648kb | C++17 | 1.4kb | 2024-09-22 22:02:41 | 2024-09-22 22:02:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 405, M = 805, P = 998244353;
int vis[N][M], f[N][M][N][2];
signed main() {
int n, m = 0; scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int S; scanf("%d", &S);
for (int j = 1, x; j <= S; ++j) {
scanf("%d", &x), vis[i][x] = 1;
m = max(m, x);
}
}
for (int i = 0; i <= m; ++i) {
f[1][i][n][0] = 1;
}
for (int i = 1; i < n; ++i) {
for (int j = 0; j <= m; ++j) if (vis[i][j]) {
for (int k = 0; k <= n; ++k) {
if (!f[i][j][k][0] && !f[i][j][k][1]) continue;
for (int l = j; l <= m; ++l) {
int nv = max(l - j - k, 0), nk = k - (l - j - nv);
if (nk >= n) --nk;
++nk;
f[i + 1][l][nk][0] = (f[i + 1][l][nk][0] + f[i][j][k][0]) % P;
f[i + 1][l][nk][1] = (f[i + 1][l][nk][1] + f[i][j][k][1]) % P;
f[i + 1][l][nk][1] = (f[i + 1][l][nk][1] + 1ll * f[i][j][k][0] * nv) % P;
}
}
}
}
int res = 0;
for (int i = 0; i <= m; ++i) if (vis[n][i]) {
for (int j = 0; j <= n; ++j) {
((res += f[n][i][j][1]) >= P) && (res -= P);
}
}
printf("%d\n", res);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8060kb
input:
5 3 1 2 3 1 2 0 4 0 2 3 4 2 2 3
output:
0
result:
ok "0"
Test #2:
score: 0
Accepted
time: 0ms
memory: 8100kb
input:
5 4 1 2 3 7 4 5 7 8 9 4 2 3 6 9 5 0 1 4 7 9 8 0 1 2 3 6 7 8 9
output:
16
result:
ok "16"
Test #3:
score: 0
Accepted
time: 2ms
memory: 8460kb
input:
10 8 1 2 3 7 15 17 18 19 11 1 2 5 8 9 10 13 16 18 19 20 12 0 1 4 5 6 7 8 9 11 16 17 19 12 0 1 3 5 9 10 11 15 16 17 18 19 6 2 8 11 15 18 19 11 0 4 6 7 8 10 11 13 16 18 19 13 1 3 4 6 8 9 10 12 13 14 15 19 20 13 2 4 5 8 9 10 11 13 14 15 16 17 20 10 2 3 5 6 8 10 13 14 18 19 12 2 3 4 5 8 9 12 13 15 16 19...
output:
27895
result:
ok "27895"
Test #4:
score: 0
Accepted
time: 2ms
memory: 8588kb
input:
10 12 0 3 4 5 6 7 8 13 14 17 19 20 15 0 1 2 4 5 6 8 9 11 12 13 14 15 18 19 9 2 7 8 9 13 15 16 18 19 17 0 1 2 3 4 5 6 7 8 9 10 11 15 16 17 18 19 17 0 1 2 4 6 7 8 9 10 11 12 14 15 16 17 19 20 17 0 1 2 3 6 8 10 11 12 13 14 15 16 17 18 19 20 15 1 3 4 6 7 9 10 11 12 13 14 15 17 19 20 16 0 1 2 3 5 6 8 9 1...
output:
625955
result:
ok "625955"
Test #5:
score: 0
Accepted
time: 0ms
memory: 8556kb
input:
10 11 0 2 3 4 6 7 8 9 10 18 19 18 1 2 3 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 17 0 1 2 3 5 6 7 8 9 10 11 13 14 15 16 18 20 18 0 1 2 3 4 5 6 8 9 10 11 12 13 16 17 18 19 20 16 0 1 2 4 5 6 7 8 9 10 11 12 13 14 17 20 20 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 15 0 1 2 3 4 7 9 10 11 14 15 16...
output:
792393
result:
ok "792393"
Test #6:
score: 0
Accepted
time: 2ms
memory: 8528kb
input:
10 18 0 1 2 4 5 6 7 8 9 10 12 13 15 16 17 18 19 20 15 2 3 4 5 6 8 9 10 12 13 14 16 17 18 19 15 0 2 3 4 5 7 10 13 14 15 16 17 18 19 20 17 0 1 2 6 7 8 9 11 12 13 14 15 16 17 18 19 20 17 0 3 4 5 6 7 8 9 10 12 13 14 16 17 18 19 20 17 0 3 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 16 0 1 2 3 4 5 6 7 10 12 ...
output:
360237
result:
ok "360237"
Test #7:
score: 0
Accepted
time: 1ms
memory: 6572kb
input:
10 18 0 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 18 19 18 0 1 2 3 4 6 7 9 10 11 13 14 15 16 17 18 19 20 15 0 2 4 5 6 7 9 11 12 13 14 16 17 19 20 18 0 1 2 3 4 6 7 8 10 11 12 13 14 15 17 18 19 20 17 0 1 2 3 5 6 7 8 10 11 12 13 14 15 16 17 18 18 0 2 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 17 0 1 2 3 5 ...
output:
5546330
result:
ok "5546330"
Test #8:
score: 0
Accepted
time: 2ms
memory: 8644kb
input:
10 17 0 1 2 3 4 7 9 10 12 13 14 15 16 17 18 19 20 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 19 0 1 2 3 4 5 6 7 8 9 12 13 14 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 19 0 1 2 3 4 5 6 7 8 9 11 12 14 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
output:
8298325
result:
ok "8298325"
Test #9:
score: 0
Accepted
time: 1ms
memory: 6536kb
input:
10 17 1 2 3 4 5 6 7 8 9 10 11 12 15 16 18 19 20 19 0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 18 19 20 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 18 0 1 2 3 4 6 8 9 10 11 12 13 14 15 16...
output:
8321362
result:
ok "8321362"
Test #10:
score: 0
Accepted
time: 0ms
memory: 6628kb
input:
10 19 0 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 18 0 1 2 3 4 5 6 7 9 10 11 12 13 14 15 17 18 20 19 0 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 19 20 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 18 19 20 18 0 1 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 20 0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 ...
output:
14615813
result:
ok "14615813"
Test #11:
score: 0
Accepted
time: 1ms
memory: 8404kb
input:
10 17 1 2 3 4 6 7 8 10 11 12 13 14 15 17 18 19 20 20 0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 19 0 1 2 3 4 5 6 7 8 9 10 11 12 14 16 17 18 19 20 19 0 1 2 3 4 5 6 7 8 9 11 12 13 15 16 17 18 19 20 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 18 19 20 17 0 2 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 ...
output:
6260430
result:
ok "6260430"
Test #12:
score: 0
Accepted
time: 2ms
memory: 10648kb
input:
10 18 0 1 3 4 5 6 7 8 9 10 12 13 14 15 16 17 19 20 19 0 1 2 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 18 0 1 2 3 4 5 6 7 8 9 10 11 12 14 16 17 18 20 18 0 1 2 3 4 6 7 8 9 11 12 14 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
output:
14649479
result:
ok "14649479"
Test #13:
score: 0
Accepted
time: 0ms
memory: 6508kb
input:
10 18 0 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 19 0 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 19 20 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 18 19 20 18 0 1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 19 20 16 1 2 6 7 8 9 10 11 12 13 14 15 16 18 19 20 19 0 1 2 3 4 6 8 9 10 11 12 13 14 15 16 17 18 19 20 19 ...
output:
11884364
result:
ok "11884364"
Test #14:
score: 0
Accepted
time: 0ms
memory: 8600kb
input:
10 18 0 1 2 3 4 5 6 7 9 10 12 13 15 16 17 18 19 20 20 0 1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 20 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 20 0 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 19 0 1 2 3 4 5 6 7 8 10 11 12 13 15 16 17 18 19 20 16 0 3 4 5 6 8 9 10 11 12 15 16 17 18 1...
output:
12608630
result:
ok "12608630"
Test #15:
score: 0
Accepted
time: 1ms
memory: 6624kb
input:
10 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 0 1 2 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 17 0 1 2 3 4 5 7 9 10 11 12 15 16 17 18 19 20 20 0 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 18 19 20 19 0 1 2 3 4 5 6 7 8 9 10 12 13 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
output:
15597786
result:
ok "15597786"
Test #16:
score: 0
Accepted
time: 2ms
memory: 8580kb
input:
10 20 0 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 18 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 19 0 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12...
output:
18162391
result:
ok "18162391"
Test #17:
score: 0
Accepted
time: 0ms
memory: 6444kb
input:
10 19 0 1 2 3 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 18 1 2 3 4 5 6 7 8 9 10 11 12 14 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 18 0 1 2 3 5 6 7 8 9 11 12 13 14 16 17 18 19 20 20 0 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 ...
output:
13636845
result:
ok "13636845"
Test #18:
score: 0
Accepted
time: 0ms
memory: 8652kb
input:
10 19 0 1 2 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 0 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 19 0 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 18 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 20 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14...
output:
23060640
result:
ok "23060640"
Test #19:
score: 0
Accepted
time: 1ms
memory: 8500kb
input:
10 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18 20 18 0 1 2 3 5 6 8 9 10 11 12 13 14 15 16 17 19 20 19 0 1 2 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 18 0 1 2 4 5 6 8 9 10 11 12 13 14 15 16 17 19 20 20 0 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 1...
output:
16391978
result:
ok "16391978"
Test #20:
score: 0
Accepted
time: 1ms
memory: 6552kb
input:
10 19 0 1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 19 20 20 0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 19 0 1 2 3 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 19 1 2 3 4 6 7 8 9 10 11 12 13 14...
output:
17643155
result:
ok "17643155"
Test #21:
score: 0
Accepted
time: 1ms
memory: 6608kb
input:
10 19 0 1 2 3 4 5 6 7 8 9 10 12 13 14 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 19 0 1 2 3 4 5 6 7 8 9 10 11 12...
output:
22529158
result:
ok "22529158"
Test #22:
score: 0
Accepted
time: 0ms
memory: 8504kb
input:
10 19 0 1 2 3 4 5 6 7 9 10 11 12 13 14 16 17 18 19 20 19 0 1 2 3 4 5 6 7 8 10 11 13 14 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 19 0 1 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 20 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
output:
23343575
result:
ok "23343575"
Test #23:
score: -100
Time Limit Exceeded
input:
400 398 1 2 3 7 15 17 18 19 22 23 26 29 30 31 34 37 39 40 41 42 43 46 47 48 49 50 51 53 58 59 61 63 64 66 68 72 73 74 78 79 80 81 82 86 92 95 99 102 103 105 109 111 112 113 115 116 118 121 123 124 127 129 130 132 134 135 136 138 139 140 141 145 146 149 151 152 155 156 157 158 160 161 162 163 164 167...