QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#750781#9740. Aho-Corasick 自动机_LSA_AC ✓83ms28800kbC++141.3kb2024-11-15 15:55:322024-11-15 15:55:32

Judging History

你现在查看的是最新测评结果

  • [2024-11-15 15:55:32]
  • 评测
  • 测评结果:AC
  • 用时:83ms
  • 内存:28800kb
  • [2024-11-15 15:55:32]
  • 提交

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