QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#809963#9536. Athlete Welcome CeremonyYipChip#WA 12ms203908kbC++232.5kb2024-12-11 18:39:212024-12-11 18:39:27

Judging History

This is the latest submission verdict.

  • [2024-12-11 18:39:27]
  • Judged
  • Verdict: WA
  • Time: 12ms
  • Memory: 203908kb
Show
  • [2024-12-11 18:39:21]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 305, mod = 998244353;
int n, q;
char s[N];
ll dp[N][N][N][3];
ll sum[N][N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i ++ ) cin >> s[i];
    int cnt = 0;
    if (s[1] == 'a') dp[1][0][0][0] = 1;
    else if (s[1] == 'b') dp[1][0][0][1] = 1;
    else if (s[1] == 'c') dp[1][0][0][2] = 1;
    else dp[1][1][0][0] = dp[1][0][1][1] = dp[1][0][0][2] = 1, cnt = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (s[i] == '?') cnt ++ ;
        for (int j = 0; j <= cnt; j ++ )
            for (int k = 0; k <= cnt; k ++ )
                for (int x = 0; x < 3; x ++ )
                {
                    if (s[i] == 'a') dp[i][j][k][0] = (dp[i - 1][j][k][1] + dp[i - 1][j][k][2]) % mod;
                    else if (s[i] == 'b') dp[i][j][k][1] = (dp[i - 1][j][k][0] + dp[i - 1][j][k][2]) % mod;
                    else if (s[i] == 'c') dp[i][j][k][2] = (dp[i - 1][j][k][0] + dp[i - 1][j][k][1]) % mod;
                    else
                    {
                        if (j) dp[i][j][k][0] = (dp[i - 1][j - 1][k][1] + dp[i - 1][j - 1][k][2]) % mod;
                        if (k) dp[i][j][k][1] = (dp[i - 1][j][k - 1][0] + dp[i - 1][j][k - 1][2]) % mod;
                        dp[i][j][k][2] = (dp[i - 1][j][k][0] + dp[i - 1][j][k][1]) % mod;
                    }
                }
    }
    for (int i = 0; i <= cnt; i ++ )
        for (int j = 0; i + j <= cnt; j ++ )
            sum[i][j][cnt - i - j] = (dp[n][i][j][0] + dp[n][i][j][1] + dp[n][i][j][2]) % mod;
    for (int i = 0; i <= cnt; i ++ )
        for (int j = 0; j <= cnt; j ++ )
            for (int k = 0; k <= cnt; k ++ )
            {
                if (i) sum[i][j][k] += sum[i - 1][j][k];
                if (j) sum[i][j][k] += sum[i][j - 1][k];
                if (k) sum[i][j][k] += sum[i][j][k - 1];
                if (i && j) sum[i][j][k] -= sum[i - 1][j - 1][k];
                if (i && k) sum[i][j][k] -= sum[i - 1][j][k - 1];
                if (j && j) sum[i][j][k] -= sum[i][j - 1][k - 1];
                if (i && j && k) sum[i][j][k] += sum[i - 1][j - 1][k - 1];
                sum[i][j][k] %= mod;
            }
                
    while (q -- )
    {
        int x, y, z;
        cin >> x >> y >> z;
        x = min(x, cnt), y = min(y, cnt), z = min(z, cnt);
        cout << (sum[x][y][z] + mod) % mod << "\n";
    }
    return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 18000kb

input:

6 3
a?b??c
2 2 2
1 1 1
1 0 2

output:

3
1
1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 22108kb

input:

6 3
??????
2 2 2
2 3 3
3 3 3

output:

30
72
96

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 5692kb

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 0ms
memory: 26172kb

input:

10 10
acab?cbaca
0 2 0
1 1 2
4 2 3
1 1 1
3 5 1
0 5 2
2 2 0
1 2 5
4 3 0
1 1 3

output:

0
1
1
1
1
0
1
1
1
1

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 26148kb

input:

10 10
?c?c?cbac?
10 5 1
5 8 7
9 2 6
5 7 1
5 2 6
5 6 5
5 10 3
9 1 10
2 5 9
1 2 9

output:

16
16
11
16
11
16
16
5
11
0

result:

ok 10 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 110172kb

input:

50 100
?abacbacab?cbcbcb?acabcbabcbcacbababc?caba?acacbca
8 3 8
2 4 8
8 7 3
0 9 2
10 8 7
7 6 5
4 10 2
6 9 3
3 6 6
9 10 8
2 5 8
8 1 0
3 5 0
1 0 6
5 0 8
6 5 5
1 7 9
7 7 10
4 7 5
6 6 4
10 1 2
4 1 7
10 0 8
7 6 3
1 9 1
4 7 2
8 4 0
8 6 1
5 10 4
5 8 2
5 8 4
4 5 9
5 2 1
1 10 9
4 10 1
8 4 3
8 9 9
8 0 1
0 8 0...

output:

8
8
8
0
8
8
6
8
8
8
8
0
0
0
1
8
4
8
8
8
2
4
1
8
1
6
0
2
8
6
8
8
1
4
2
8
8
0
0
8
2
0
8
8
8
4
8
8
8
8
2
0
0
4
8
8
1
8
7
6
7
0
8
8
8
0
4
7
8
4
0
8
0
4
8
8
8
7
8
4
7
2
8
8
8
0
2
2
8
8
8
4
4
0
8
0
8
8
1
1

result:

ok 100 lines

Test #7:

score: 0
Accepted
time: 0ms
memory: 130792kb

input:

50 100
b????????bca?????c?b??ca?acac?b?b???ca?ab???a?a???
35 43 36
12 49 47
7 11 34
38 44 22
42 17 10
49 8 38
18 26 44
6 18 14
28 29 6
48 32 47
29 15 48
1 5 33
24 17 18
10 27 32
19 10 34
2 23 9
14 24 39
46 12 34
9 49 26
21 8 46
43 43 3
31 16 2
8 27 7
24 41 35
17 25 31
0 13 47
24 31 23
33 40 30
36 39...

output:

34272000
31599360
497244
34272000
17637520
12290752
34272000
93044
415832
34272000
34272000
0
34272000
16360704
27933952
0
34272000
33886976
7896832
12290752
718
24
0
34272000
34272000
0
34272000
34272000
34272000
32254720
0
5666944
34256640
34272000
34272000
12290752
30493248
34256640
20630016
0
10...

result:

ok 100 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 170008kb

input:

100 1000
c?cbababcabacbacbacacbacabcbabababacababcbcab?cbabacbacbcbcacbab?bcabcbcababcacbabacbcb?babcbab?baca
13 11 4
4 17 20
14 5 2
16 14 15
8 12 17
19 5 11
5 17 12
20 7 6
19 10 1
6 5 0
13 1 9
7 17 1
20 4 16
11 12 18
19 2 16
18 1 11
19 16 3
7 1 0
6 9 16
6 9 16
6 20 7
0 16 20
1 2 8
16 5 20
18 14 18
...

output:

16
15
14
16
16
16
16
16
8
2
16
8
16
16
16
16
16
2
16
16
16
0
1
16
16
5
1
5
16
16
16
16
16
15
16
13
16
15
2
16
16
1
8
16
16
16
15
0
16
15
16
16
16
16
8
8
16
16
16
16
16
16
8
16
16
1
8
8
16
16
1
16
1
0
16
2
2
16
7
16
16
8
16
16
16
16
1
16
14
16
16
16
16
5
16
16
14
16
11
16
15
11
2
1
8
16
16
7
16
5
16
...

result:

ok 1000 lines

Test #9:

score: -100
Wrong Answer
time: 12ms
memory: 203908kb

input:

100 1000
?????c??????????????????????????b???a????a?????????????????????????c????????????????????????????????
43 38 20
27 40 32
39 27 33
28 50 43
50 3 46
38 46 14
42 48 10
45 25 28
49 10 49
38 17 42
41 49 22
41 18 44
46 47 25
17 44 35
34 43 22
47 42 32
32 44 40
36 41 24
45 38 45
49 44 18
42 34 32
43...

output:

804458366
986514507
631676168
668774326
10104
806873682
457652893
556612659
833031739
194151457
769278037
274041326
594216165
183174115
939173449
604062764
737118944
281846238
379026979
660541372
959207727
575057371
385668393
989871351
166230586
907706324
523034330
586950612
67939963
816607907
42635...

result:

wrong answer 1st lines differ - expected: '490475656', found: '804458366'
English 繁體中文 简体中文

Server Time: 2025-02-06 22:07:17 | OpenSource Project