QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#747571#9536. Athlete Welcome CeremonyKDreamWA 32ms31336kbC++204.3kb2024-11-14 17:33:392024-11-14 17:33:40

Judging History

This is the latest submission verdict.

  • [2024-11-14 17:33:40]
  • Judged
  • Verdict: WA
  • Time: 32ms
  • Memory: 31336kb
Show
  • [2024-11-14 17:33:39]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int mod = 1e9 + 7; 
int dp[505][505][505][3];
int ans[155][155][155];
int cnt[4];
int n,m;
void init ()
{
    cin >> n >> m;
    string s;
    cin >> s;
    s = " " + s;
    
    for (int i = 1;i <= n;i ++)
    {
        cnt[s[i] - 'a'] += s[i] != '?';
    }
    if (s[1] == '?')
        dp[1][1][0][0] = dp[1][0][1][1] = dp[1][0][0][2] = 1;
    else if (s[1] == 'a')
        dp[1][1][0][0] = 1;
    else if (s[1] == 'b')
        dp[1][0][1][1] = 1;
    else if (s[1] == 'c')
        dp[1][0][0][2] = 1;
    
    for (int i = 1;i <= n;i ++)
    {
        for (int j = 0;j <= (i + 1) / 2;j ++)
        {
            for (int k = 0;k <= (i + 1) / 2 && j + k <= i;k ++)
            {
                int l = i - j - k;
                if (l > (i + 1) / 2) continue;

                if (s[i] == 'a')
                {
                    if (j)
                    {
                        dp[i][j][k][0] = dp[i][j][k][0] + dp[i - 1][j - 1][k][1] + dp[i - 1][j - 1][k][2];
                        dp[i][j][k][0] %= mod;
                    }
                }
                else if (s[i] == 'b')
                {
                    if (k)
                    {
                        dp[i][j][k][1] = dp[i][j][k][1] + dp[i - 1][j][k - 1][0] + dp[i - 1][j][k - 1][2];
                        dp[i][j][k][1] %= mod;
                    }
                }
                else if (s[i] == 'c')
                {
                    if (l)
                    {
                        dp[i][j][k][2] = dp[i][j][k][2] + dp[i - 1][j][k][0] + dp[i - 1][j][k][1];
                        dp[i][j][k][2] %= mod;
                    }
                }
                else
                {
                    if (j)
                    {
                        dp[i][j][k][0] = dp[i][j][k][0] + dp[i - 1][j - 1][k][1] + dp[i - 1][j - 1][k][2];
                        dp[i][j][k][0] %= mod;
                    }
                    if (k)
                    {
                        dp[i][j][k][1] = dp[i][j][k][1] + dp[i - 1][j][k - 1][0] + dp[i - 1][j][k - 1][2];
                        dp[i][j][k][1] %= mod;
                    }
                    if (l)
                    {
                        dp[i][j][k][2] = dp[i][j][k][2] + dp[i - 1][j][k][0] + dp[i - 1][j][k][1];
                        dp[i][j][k][2] %= mod;
                    }
                }
            }
        }
    }
    
   
    for (int j = 0;j <= (n + 1) / 2;j ++)
    {
        for (int k = 0;k <= (n + 1) / 2 && j + k <= n;k ++)
        {

            int l = n - j - k;
            if (l > (n + 1) / 2) continue;

            ans[j][k][l] += dp[n][j][k][0] + dp[n][j][k][1] + dp[n][j][k][2];
            ans[j][k][l] %= mod;
        }
    }
    

    for (int i = 0;i <= 152;i ++)
    {
        for (int j = 0;j <= 152;j ++)
        {
            for (int k = 0;k <= 152;k ++)
            {
                if (i)
                {
                    ans[i][j][k] += ans[i - 1][j][k];
                    ans[i][j][k] %= mod;
                } 
            }
        }
    }
    for (int i = 0;i <= 152;i ++)
    {
        for (int j = 0;j <= 152;j ++)
        {
            for (int k = 0;k <= 152;k ++)
            {
                if (j)
                {
                    ans[i][j][k] += ans[i][j - 1][k];
                    ans[i][j][k] %= mod;
                } 
            }
        }
    }
    for (int i = 0;i <= 152;i ++)
    {
        for (int j = 0;j <= 152;j ++)
        {
            for (int k = 0;k <= 152;k ++)
            {
                if (k)
                {
                    ans[i][j][k] += ans[i][j][k - 1];
                    ans[i][j][k] %= mod;
                } 
            }
        }
    }
    
}
void _Z()
{   

    init();

    while (m --)
    {
        int x, y, z;
        cin >> x >> y >> z;
        x = min(150,x + cnt[0]);
        y = min(150,y + cnt[1]);
        z = min(150,z + cnt[2]);
        cout << ans[x][y][z] << "\n";
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
    {
        _Z();
    }
    return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 21ms
memory: 20256kb

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: 20ms
memory: 20100kb

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: 20ms
memory: 19960kb

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 28ms
memory: 20104kb

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: 29ms
memory: 20060kb

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: 31ms
memory: 23000kb

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: 23ms
memory: 22904kb

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: 22ms
memory: 31196kb

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: 32ms
memory: 31336kb

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:

195508388
259088039
939792871
858846490
10104
334198754
479284703
174283993
18944427
659694548
894876281
515985973
342761527
182802705
215438611
24903472
898235886
313982884
440599794
337549965
39088634
527160619
688006832
529480730
906092786
448494161
718236644
816152457
705467745
176823209
6667784...

result:

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

伺服器時間: 2025-02-07 00:37:36 | 開源專案