QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #760245 | #9740. Aho-Corasick 自动机 | Symmetree | AC ✓ | 56ms | 8308kb | C++17 | 1.1kb | 2024-11-18 15:48:45 | 2024-11-18 15:48:55 |
Judging History
answer
#include<bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
const int N = 105, mod = 998244353;
int n, m, d, f[N][N][N], g[N][N], c[N][N];
signed main() {
scanf("%d%d%d", &n, &m, &d);
for(int i = 0; i <= m; ++i) c[i][0] = c[i][i] = 1;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= m; ++j)
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
g[0][0] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= n; ++j)
for(int k = 0; k <= std::min(m, j); ++k)
g[i][j] = (g[i][j] + 1ll * g[i - 1][j - k] * c[m][k] % mod) % mod;
f[0][1][1] = 1;
for(int i = 1; i <= d; ++i)
for(int j = 1; j <= n; ++j)
for(int k = 1; k <= j; ++k)
for(int t = 1; t <= j - k; ++t)
f[i][j][k] = (f[i][j][k] + 1ll * f[i - 1][j - k][t] * g[t][k] % mod) % mod;
int ans = 0;
for(int i = 0; i <= d; ++i)
for(int j = 1; j <= n; ++j)
ans += f[i][n][j], ans %= mod;
printf("%d\n", ans);
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3812kb
input:
3 2 2
output:
5
result:
ok answer is '5'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
4 2 2
output:
6
result:
ok answer is '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4336kb
input:
30 30 30
output:
286511539
result:
ok answer is '286511539'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
13 13 13
output:
818093168
result:
ok answer is '818093168'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4316kb
input:
30 25 25
output:
730504816
result:
ok answer is '730504816'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4304kb
input:
29 29 29
output:
892409454
result:
ok answer is '892409454'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4124kb
input:
15 30 28
output:
505511076
result:
ok answer is '505511076'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4088kb
input:
20 10 30
output:
250115604
result:
ok answer is '250115604'
Test #10:
score: 0
Accepted
time: 1ms
memory: 4156kb
input:
20 30 30
output:
623437187
result:
ok answer is '623437187'
Test #11:
score: 0
Accepted
time: 54ms
memory: 8308kb
input:
100 100 100
output:
933606371
result:
ok answer is '933606371'
Test #12:
score: 0
Accepted
time: 56ms
memory: 8032kb
input:
100 95 95
output:
368609759
result:
ok answer is '368609759'
Test #13:
score: 0
Accepted
time: 50ms
memory: 8168kb
input:
95 100 100
output:
691641619
result:
ok answer is '691641619'
Test #14:
score: 0
Accepted
time: 45ms
memory: 8032kb
input:
95 97 98
output:
517539873
result:
ok answer is '517539873'
Test #15:
score: 0
Accepted
time: 13ms
memory: 4900kb
input:
94 67 23
output:
601572539
result:
ok answer is '601572539'
Extra Test:
score: 0
Extra Test Passed