QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#750129 | #9740. Aho-Corasick 自动机 | propane | AC ✓ | 76ms | 3752kb | C++20 | 989b | 2024-11-15 12:52:05 | 2024-11-15 12:52:05 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
const int mod = 998244353;
void add(int &a, int b){
a += b;
if (a >= mod) a -= mod;
}
int mul(int a, int b){
return 1LL * a * b % mod;
}
int dp[105][105], tmp[105];
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n, m, d;
cin >> n >> m >> d;
dp[d][0] = dp[d][1] = 1;
for(int i = d - 1; i >= 0; i--){
dp[i][1] = 1;
for(int j = 0; j < m; j++){
memset(tmp, 0, sizeof tmp);
for(int k = 1; k <= n; k++){
for(int t = 0; k + t <= n; t++){
add(tmp[k + t], mul(dp[i][k], dp[i + 1][t]));
}
}
swap(dp[i], tmp);
}
dp[i][0] = 1;
}
cout << dp[0][n] << '\n';
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3664kb
input:
3 2 2
output:
5
result:
ok answer is '5'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
4 2 2
output:
6
result:
ok answer is '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
30 30 30
output:
286511539
result:
ok answer is '286511539'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
13 13 13
output:
818093168
result:
ok answer is '818093168'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
30 25 25
output:
730504816
result:
ok answer is '730504816'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
29 29 29
output:
892409454
result:
ok answer is '892409454'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
15 30 28
output:
505511076
result:
ok answer is '505511076'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
20 10 30
output:
250115604
result:
ok answer is '250115604'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
20 30 30
output:
623437187
result:
ok answer is '623437187'
Test #11:
score: 0
Accepted
time: 76ms
memory: 3752kb
input:
100 100 100
output:
933606371
result:
ok answer is '933606371'
Test #12:
score: 0
Accepted
time: 69ms
memory: 3708kb
input:
100 95 95
output:
368609759
result:
ok answer is '368609759'
Test #13:
score: 0
Accepted
time: 69ms
memory: 3628kb
input:
95 100 100
output:
691641619
result:
ok answer is '691641619'
Test #14:
score: 0
Accepted
time: 61ms
memory: 3708kb
input:
95 97 98
output:
517539873
result:
ok answer is '517539873'
Test #15:
score: 0
Accepted
time: 11ms
memory: 3676kb
input:
94 67 23
output:
601572539
result:
ok answer is '601572539'
Extra Test:
score: 0
Extra Test Passed