QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #782064 | #9740. Aho-Corasick 自动机 | Zpair | AC ✓ | 123ms | 8036kb | C++20 | 779b | 2024-11-25 18:42:36 | 2024-11-25 18:42:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
void add(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
}
const int N=105;
int f[N][N][N],g[N][N],n,m,d;
int C[N][N];
int main(){
cin>>n>>m>>d;
for(int i=0;i<N;++i)
C[i][i]=C[i][0]=1;
for(int i=1;i<N;++i)
for(int j=1;j<=i;++j)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
g[0][0]=1;
for(int i=1;i<=n;++i)
for(int j=0;j<=n;++j)
for(int k=0;k<=j;++k)
add(g[i][j],(ll)g[i-1][j-k]*C[m][k]%mod);
//i个点得到j
f[0][1][1]=1;
for(int i=1;i<=d;++i)
for(int j=0;j<=n;++j)
for(int k=0;k<=j;++k)
for(int l=0;l<=n;++l)
add(f[i][j][k],(ll)f[i-1][j-k][l]*g[l][k]%mod);
int ans=0;
for(int i=0;i<=n;++i)
add(ans,f[d][n][i]);
cout<<ans;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
input:
3 2 2
output:
5
result:
ok answer is '5'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
4 2 2
output:
6
result:
ok answer is '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 2ms
memory: 4100kb
input:
30 30 30
output:
286511539
result:
ok answer is '286511539'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
13 13 13
output:
818093168
result:
ok answer is '818093168'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
30 25 25
output:
730504816
result:
ok answer is '730504816'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4136kb
input:
29 29 29
output:
892409454
result:
ok answer is '892409454'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3952kb
input:
15 30 28
output:
505511076
result:
ok answer is '505511076'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4060kb
input:
20 10 30
output:
250115604
result:
ok answer is '250115604'
Test #10:
score: 0
Accepted
time: 1ms
memory: 4100kb
input:
20 30 30
output:
623437187
result:
ok answer is '623437187'
Test #11:
score: 0
Accepted
time: 123ms
memory: 8028kb
input:
100 100 100
output:
933606371
result:
ok answer is '933606371'
Test #12:
score: 0
Accepted
time: 109ms
memory: 7800kb
input:
100 95 95
output:
368609759
result:
ok answer is '368609759'
Test #13:
score: 0
Accepted
time: 101ms
memory: 8036kb
input:
95 100 100
output:
691641619
result:
ok answer is '691641619'
Test #14:
score: 0
Accepted
time: 92ms
memory: 7928kb
input:
95 97 98
output:
517539873
result:
ok answer is '517539873'
Test #15:
score: 0
Accepted
time: 21ms
memory: 4760kb
input:
94 67 23
output:
601572539
result:
ok answer is '601572539'
Extra Test:
score: 0
Extra Test Passed