QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#789699#9740. Aho-Corasick 自动机ValenciaTravis#AC ✓182ms3952kbC++201.1kb2024-11-27 21:30:012024-11-27 21:30:04

Judging History

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

  • [2024-11-27 21:30:04]
  • 评测
  • 测评结果:AC
  • 用时:182ms
  • 内存:3952kb
  • [2024-11-27 21:30:01]
  • 提交

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