QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#789699 | #9740. Aho-Corasick 自动机 | ValenciaTravis# | AC ✓ | 182ms | 3952kb | C++20 | 1.1kb | 2024-11-27 21:30:01 | 2024-11-27 21:30:04 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define MAXN 105
#define ll long long
const ll mod = 998244353;
int n, m, d;
ll f[MAXN][MAXN], g[MAXN][MAXN], tmp[MAXN][MAXN][2];
int main() {
cin>>n>>m>>d; d++;
f[0][0] = 1; g[0][0] = 1;
for(int i=1;i<=d;i++) {
memset(tmp, 0, sizeof(tmp));
tmp[0][0][i==1] = 1;
for(int j=1;j<=m;j++) {
for(int k=0;k<n;k++) {
for(int l=0;l<=k;l++) {
if(i >= 2) (tmp[j][k][0] += tmp[j-1][k-l][0] * g[i-2][l]) %= mod;
(tmp[j][k][1] += tmp[j-1][k-l][1] * g[i-1][l] + tmp[j-1][k-l][0] * f[i-1][l]) %= mod;
}
// printf("tmp[%d][%d] = %lld, %lld\n", j, k, tmp[j][k][0], tmp[j][k][1]);
}
}
for(int j=1;j<=n;j++) f[i][j] = tmp[m][j-1][1], g[i][j] = (g[i-1][j] + f[i][j]) % mod;
g[i][0] = 1;
// for(int j=1;j<=n;j++) {
// printf("f[%d][%d] = %lld, g[%d][%d] = %lld\n", i, j, f[i][j], i, j, g[i][j]);
// }
}
cout << g[d][n] << '\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3844kb
input:
3 2 2
output:
5
result:
ok answer is '5'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
4 2 2
output:
6
result:
ok answer is '6'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3840kb
input:
30 30 30
output:
286511539
result:
ok answer is '286511539'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
13 13 13
output:
818093168
result:
ok answer is '818093168'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3816kb
input:
30 25 25
output:
730504816
result:
ok answer is '730504816'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
29 29 29
output:
892409454
result:
ok answer is '892409454'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3816kb
input:
15 30 28
output:
505511076
result:
ok answer is '505511076'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
20 10 30
output:
250115604
result:
ok answer is '250115604'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3856kb
input:
20 30 30
output:
623437187
result:
ok answer is '623437187'
Test #11:
score: 0
Accepted
time: 182ms
memory: 3952kb
input:
100 100 100
output:
933606371
result:
ok answer is '933606371'
Test #12:
score: 0
Accepted
time: 164ms
memory: 3944kb
input:
100 95 95
output:
368609759
result:
ok answer is '368609759'
Test #13:
score: 0
Accepted
time: 164ms
memory: 3900kb
input:
95 100 100
output:
691641619
result:
ok answer is '691641619'
Test #14:
score: 0
Accepted
time: 151ms
memory: 3880kb
input:
95 97 98
output:
517539873
result:
ok answer is '517539873'
Test #15:
score: 0
Accepted
time: 26ms
memory: 3824kb
input:
94 67 23
output:
601572539
result:
ok answer is '601572539'
Extra Test:
score: 0
Extra Test Passed