QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#734636#9536. Athlete Welcome CeremonyDixiky_215TL 72ms366020kbC++203.4kb2024-11-11 13:31:492024-11-11 13:31:50

Judging History

This is the latest submission verdict.

  • [2024-11-11 13:31:50]
  • Judged
  • Verdict: TL
  • Time: 72ms
  • Memory: 366020kb
Show
  • [2024-11-11 13:31:49]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MAXN=5e5+7;
int t;
int a[MAXN];
int n,m;
string b;
ll dp[2][303][303][303][4];
ll ans[303][303][303];
ll mod=1e9+7LL;
int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    
    cin>>n>>m;
    cin>>b;
    b=' '+b;
    
    if(b[1]=='?')
    {
        dp[0][0][0][1][3]=1LL;
        dp[0][0][1][0][2]=1LL;
        dp[0][1][0][0][1]=1LL;
    }
    else
    {
        dp[0][0][0][0][b[1]-'a'+1]=1LL;
    }
    for(int i=2;i<=n;i++)
    {
        if(b[i]=='?')
        {
            for(int s1=0;s1<=i;s1++)
            {
                for(int s2=0;s2<=i-s1;s2++)
                {
                    for(int s3=0;s3<=i-s1-s2;s3++)
                    {
                        if(s1>0) dp[1][s1][s2][s3][1]+=dp[0][s1-1][s2][s3][2]+dp[0][s1-1][s2][s3][3];
                        if(s2>0) dp[1][s1][s2][s3][2]+=dp[0][s1][s2-1][s3][1]+dp[0][s1][s2-1][s3][3];
                        if(s3>0) dp[1][s1][s2][s3][3]+=dp[0][s1][s2][s3-1][1]+dp[0][s1][s2][s3-1][2];
                        dp[1][s1][s2][s3][1]%=mod;
                        dp[1][s1][s2][s3][2]%=mod;
                        dp[1][s1][s2][s3][3]%=mod;
                    }
                }
            }
        }
        else
        {
            for(int s1=0;s1<=i;s1++)
            {
                for(int s2=0;s2<=i-s1;s2++)
                {
                    for(int s3=0;s3<=i-s1-s2;s3++)
                    {
                        if(b[i]=='a')
                        {
                            dp[1][s1][s2][s3][1]+=dp[0][s1][s2][s3][2]+dp[0][s1][s2][s3][3];
                            dp[1][s1][s2][s3][1]%=mod;
                        }
                        else if(b[i]=='b')
                        {
                            dp[1][s1][s2][s3][2]+=dp[0][s1][s2][s3][1]+dp[0][s1][s2][s3][3];
                            dp[1][s1][s2][s3][2]%=mod;
                        }
                        else
                        {
                            dp[1][s1][s2][s3][3]+=dp[0][s1][s2][s3][1]+dp[0][s1][s2][s3][2];
                            dp[1][s1][s2][s3][3]%=mod;
                        }
                    }
                }
            }
        }

        for(int s1=0;s1<=i;s1++)
        {
            for(int s2=0;s2<=i-s1;s2++)
            {
                for(int s3=0;s3<=i-s1-s2;s3++)
                {
                    for(int k=1;k<=3;k++)
                    {
                        dp[0][s1][s2][s3][k]=dp[1][s1][s2][s3][k];
                        dp[1][s1][s2][s3][k]=0;
                    }
                }
            }
        }
    }
    // cerr<<dp[0][1][1][1]<<" sad"<<endl;
    for(int i=1;i<=n+1;i++)
    {
        for(int j=1;j<=n+1;j++)
        {
            for(int k=1;k<=n+1;k++)
            {
                int s1=i-1,s2=j-1,s3=k-1;
                ll sumk=dp[0][s1][s2][s3][1]+dp[0][s1][s2][s3][2]+dp[0][s1][s2][s3][3];
                sumk+=ans[i-1][j][k]+ans[i][j-1][k]+ans[i][j][k-1];
                sumk-=ans[i-1][j-1][k]+ans[i-1][j][k-1]+ans[i][j-1][k-1];
                sumk+=ans[i-1][j-1][k-1];
                ans[i][j][k]=(sumk%mod+mod)%mod;
            }
        }
    }
    while(m--)
    {
        int s1,s2,s3;
        cin>>s1>>s2>>s3;
        cout<<ans[s1+1][s2+1][s3+1]<<'\n';
    }
    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 34376kb

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: 9712kb

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

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

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: 3ms
memory: 22936kb

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: 3ms
memory: 50500kb

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

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: 72ms
memory: 113440kb

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: 0
Accepted
time: 68ms
memory: 366020kb

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:

490475656
143989836
119661929
707864467
10104
219100551
479284703
764218529
903846231
659694548
204287063
105920502
191779504
182802705
215438611
938692318
797581204
903917420
893995828
287222624
578695829
95654849
457810426
709349795
85961844
923330494
783007506
111119718
295402274
241594071
551680...

result:

ok 1000 lines

Test #10:

score: 0
Accepted
time: 67ms
memory: 252704kb

input:

100 1000
c???cacacbcab?cb?acb???ac?bab?bcbcbc?c?bcbcaba??b?ba?c?aca?a?bac?cbcbcba??ca?b????ac?baba?ab?cba?c?c
99 70 32
52 98 84
12 78 77
84 8 87
16 36 0
48 70 100
25 4 15
95 54 35
33 35 90
20 4 69
6 11 76
27 96 48
16 24 18
99 48 1
43 54 35
9 81 75
27 58 52
50 94 14
29 67 27
59 68 53
42 31 46
12 90 2...

output:

380160
380160
226896
64156
0
380160
92
380160
380160
92
0
380160
379648
0
380160
22500
380160
380160
380160
380160
380160
226896
380160
380160
226896
0
380160
380160
380160
380160
152672
380160
5624
226896
380160
380160
379648
0
380160
380160
366848
380160
226896
380160
92
374912
5624
380160
380160
...

result:

ok 1000 lines

Test #11:

score: -100
Time Limit Exceeded

input:

300 100000
abcacacbabacbcababcacacb?babacbcbacbcababcbcbabcacbcbacacabacacacbacbcbcacbabacbcbcbabcacbababcabcabcabababacbcacbacabcbacbacacacbababababacbcababcbcacacbcbabacabcabababcabacbcbcbabcabacbabacacbcbcacacacbcabcbabcbcabababababcacabcabababcbcbcbcbcabacbabacbabcacbcababacacbcbababababcacacaba...

output:

result:
English 繁體中文 简体中文

Server Time: 2025-02-07 04:14:16 | OpenSource Project