QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#759111 | #9740. Aho-Corasick 自动机 | fstqwq# | WA | 0ms | 3640kb | C++20 | 1.2kb | 2024-11-17 21:44:41 | 2024-11-17 21:44:42 |
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;
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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
input:
3 2 2
output:
5
result:
ok answer is '5'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
4 2 2
output:
6
result:
ok answer is '6'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3592kb
input:
1 1 1
output:
0
result:
wrong answer expected '1', found '0'