QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#759112 | #9740. Aho-Corasick 自动机 | fstqwq# | AC ✓ | 9ms | 11728kb | C++20 | 1.2kb | 2024-11-17 21:45:10 | 2024-11-17 21:45:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 998244353;
int main() {
int n, m, d;
cin >> n >> m >> d;
vector <vector <LL>> C(n * m + 1, vector <LL> (n + 1));
for (int i = 0; i <= n * m; i++) {
C[i][0] = 1;
for (int j = 1; j <= min(i, n); j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
// cerr << i << " " << j << " " << C[i][j] << endl;
}
}
vector < vector <LL> > f(n + 1, vector <LL> (n + 1));
f[1][1] = 1;
LL ans = 0;
if (n == 1) ans += 1;
for (int i = 1; i <= d; i++) {
vector < vector <LL> > g(n + 1, vector <LL> (n + 1));
for (int j = 1; j <= n; j++) { // used j nodes
for (int k = 1; k <= n; k++) { // currently k nodes
if (f[j][k] == 0) continue;
for (int l = 1; l <= min(k * m, n - j); l++) {
g[j + l][l] = (g[j + l][l] + f[j][k] * C[k * m][l]) % MOD;
}
}
}
f = move(g);
for (int j = 1; j <= n; j++) {
ans = (ans + f[n][j]) % MOD;
}
}
ans %= MOD;
ans += MOD;
ans %= MOD;
cout << ans << endl;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3488kb
input:
3 2 2
output:
5
result:
ok answer is '5'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
4 2 2
output:
6
result:
ok answer is '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
30 30 30
output:
286511539
result:
ok answer is '286511539'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
13 13 13
output:
818093168
result:
ok answer is '818093168'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
30 25 25
output:
730504816
result:
ok answer is '730504816'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
29 29 29
output:
892409454
result:
ok answer is '892409454'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
15 30 28
output:
505511076
result:
ok answer is '505511076'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
20 10 30
output:
250115604
result:
ok answer is '250115604'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
20 30 30
output:
623437187
result:
ok answer is '623437187'
Test #11:
score: 0
Accepted
time: 7ms
memory: 11728kb
input:
100 100 100
output:
933606371
result:
ok answer is '933606371'
Test #12:
score: 0
Accepted
time: 7ms
memory: 11576kb
input:
100 95 95
output:
368609759
result:
ok answer is '368609759'
Test #13:
score: 0
Accepted
time: 6ms
memory: 11024kb
input:
95 100 100
output:
691641619
result:
ok answer is '691641619'
Test #14:
score: 0
Accepted
time: 9ms
memory: 10808kb
input:
95 97 98
output:
517539873
result:
ok answer is '517539873'
Test #15:
score: 0
Accepted
time: 6ms
memory: 8668kb
input:
94 67 23
output:
601572539
result:
ok answer is '601572539'
Extra Test:
score: 0
Extra Test Passed