QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#750781 | #9740. Aho-Corasick 自动机 | _LSA_ | AC ✓ | 83ms | 28800kb | C++14 | 1.3kb | 2024-11-15 15:55:32 | 2024-11-15 15:55:32 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
using namespace std;
ll read(){
ll X = 0 ,r = 1;
char ch = getchar();
while(!isdigit(ch) && ch != '-') ch = getchar();
if(ch == '-') r = -1,ch = getchar();
while(isdigit(ch)) X = X*10+ch-'0',ch = getchar();
return X*r;
}
const int N = 110;
const int mod = 998244353;
ll fac[1000100],inv[1000100];
ll fpow(ll x,ll k){
ll res = 1;
while(k){
if(k & 1)
res = res*x%mod;
x = x*x%mod;
k >>= 1;
}
return res;
}
void init(int n = 1e6){
fac[0] = inv[0] = 1;
for(int i=1;i<=n;i++) fac[i] = fac[i-1]*i%mod;
inv[n] = fpow(fac[n],mod-2);
for(int i=n-1;i;i--) inv[i] = inv[i+1]*(i+1)%mod;
}
ll C(int x,int y){
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int n,m,d;
ll f[N][N][N];
int main(){
init();
n = read(); m = read(); d = read();
f[0][1][1] = 1;
for(int i=0;i<d;i++) for(int j=1;j<=n;j++)
for(int k=0;k<=j;k++) for(int x=0;x<=min(m*k,n-j);x++)
f[i+1][j+x][x] = (f[i+1][j+x][x]+C(m*k,x)*f[i][j][k]%mod)%mod;
ll ans = 0;
for(int i=0;i<=n;i++) ans = (ans+f[d][n][i])%mod;
cout << ans;
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 19804kb
input:
3 2 2
output:
5
result:
ok answer is '5'
Test #2:
score: 0
Accepted
time: 7ms
memory: 19288kb
input:
4 2 2
output:
6
result:
ok answer is '6'
Test #3:
score: 0
Accepted
time: 7ms
memory: 20236kb
input:
1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 7ms
memory: 21620kb
input:
30 30 30
output:
286511539
result:
ok answer is '286511539'
Test #5:
score: 0
Accepted
time: 11ms
memory: 19464kb
input:
13 13 13
output:
818093168
result:
ok answer is '818093168'
Test #6:
score: 0
Accepted
time: 3ms
memory: 21968kb
input:
30 25 25
output:
730504816
result:
ok answer is '730504816'
Test #7:
score: 0
Accepted
time: 7ms
memory: 20948kb
input:
29 29 29
output:
892409454
result:
ok answer is '892409454'
Test #8:
score: 0
Accepted
time: 7ms
memory: 19824kb
input:
15 30 28
output:
505511076
result:
ok answer is '505511076'
Test #9:
score: 0
Accepted
time: 10ms
memory: 19740kb
input:
20 10 30
output:
250115604
result:
ok answer is '250115604'
Test #10:
score: 0
Accepted
time: 8ms
memory: 20620kb
input:
20 30 30
output:
623437187
result:
ok answer is '623437187'
Test #11:
score: 0
Accepted
time: 83ms
memory: 28756kb
input:
100 100 100
output:
933606371
result:
ok answer is '933606371'
Test #12:
score: 0
Accepted
time: 80ms
memory: 28436kb
input:
100 95 95
output:
368609759
result:
ok answer is '368609759'
Test #13:
score: 0
Accepted
time: 77ms
memory: 28252kb
input:
95 100 100
output:
691641619
result:
ok answer is '691641619'
Test #14:
score: 0
Accepted
time: 76ms
memory: 28800kb
input:
95 97 98
output:
517539873
result:
ok answer is '517539873'
Test #15:
score: 0
Accepted
time: 23ms
memory: 22832kb
input:
94 67 23
output:
601572539
result:
ok answer is '601572539'
Extra Test:
score: 0
Extra Test Passed