QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#767732#9536. Athlete Welcome Ceremonyjdyt11WA 207ms283828kbC++233.0kb2024-11-20 21:56:212024-11-20 21:56:25

Judging History

This is the latest submission verdict.

  • [2024-11-20 21:56:25]
  • Judged
  • Verdict: WA
  • Time: 207ms
  • Memory: 283828kb
Show
  • [2024-11-20 21:56:21]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define inf 0x3f3f3f3f
#define ull unsigned long long
#define pll pair<ll,ll>
#define ls d*2
#define rs d*2+1
#define mid (l+r)/2
#define lowbit(x) (x&(-x))
//#define endl "\n"
#define all(x) x.begin(),x.end()
#define int long long
//mt19937 seed;
//uniform_int_distribution<int>num(0,2e9);
const int N=1e6+10;
const int M=33;


int dp[310][310][310][3];
int f[310][310][310];
int cnt[310];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int _=1;//cin>>_;
    while(_--){
        int n,q;
        cin>>n>>q;
        string s;
        cin>>s;
        s='.'+s;
        int mod=1e9+7;
        for(int i=1;i<=n;i++)cnt[i]=cnt[i-1]+(s[i]=='?');
        for(int i=1;i<=n;i++){
            if(i==1){
                if(s[i]=='a')dp[1][0][0][0]=1;
                else if(s[i]=='b')dp[1][0][0][1]=1;
                else if(s[i]=='c')dp[1][0][0][2]=1;
                else dp[1][1][0][0]=dp[1][0][1][1]=dp[1][0][0][2]=1;
            }
            else{
                for(int j=0;j<=cnt[i];j++){
                    for(int k=0;k+j<=cnt[i];k++){
                        if(s[i]=='a')dp[i][j][k][0]+=dp[i-1][j][k][1]+dp[i-1][j][k][2],dp[i][j][k][0]%=mod;
                        else if(s[i]=='b')dp[i][j][k][1]+=dp[i-1][j][k][0]+dp[i-1][j][k][2],dp[i][j][k][1]%=mod;
                        else if(s[i]=='c')dp[i][j][k][2]+=dp[i-1][j][k][1]+dp[i-1][j][k][0],dp[i][j][k][2]%=mod;
                        else{
                            if(j)dp[i][j][k][0]+=dp[i-1][j-1][k][1]+dp[i-1][j-1][k][2];
                            if(k)dp[i][j][k][1]+=dp[i-1][j][k-1][0]+dp[i-1][j][k-1][2];
                            if(cnt[i]-j-k)dp[i][j][k][2]+=dp[i-1][j][k][1]+dp[i-1][j][k][0];
                            dp[i][j][k][0]%=mod;
                            dp[i][j][k][1]%=mod;
                            dp[i][j][k][2]%=mod;
                        }
                    }
                }
            }
        }
        for(int i=0;i<=cnt[n];i++){
            for(int j=0;j+i<=cnt[n];j++){
                f[i][j][cnt[n]-i-j]=(dp[n][i][j][0]+dp[n][i][j][1]+dp[n][i][j][2])%mod;
            }
        }
        for(int i=0;i<=300;i++){
            for(int j=0;j<=300;j++){
                for(int k=0;k<=300;k++){
                    if(i)f[i][j][k]+=f[i-1][j][k];
                    if(j)f[i][j][k]+=f[i][j-1][k];
                    if(k)f[i][j][k]+=f[i][j][k-1];
                    if(i&&j)f[i][j][k]-=f[i-1][j-1][k];
                    if(i&&k)f[i][j][k]-=f[i-1][j][k-1];
                    if(k&&j)f[i][j][k]-=f[i][j-1][k-1];
                    if(i&&j&&k)f[i][j][k]+=f[i-1][j-1][k-1];
                    f[i][j][k]=(f[i][j][k]+mod)%mod;
                }
            }
        }
        while(q--){
            int a,b,c;
            cin>>a>>b>>c;
            cout<<f[a][b][c]<<endl;
        }
    }
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 163ms
memory: 226308kb

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

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

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 171ms
memory: 226316kb

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

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

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

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

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

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:

wrong answer 170th lines differ - expected: '931481592', found: '-68518415'
English 繁體中文 简体中文

服务器时间: 2025-02-07 00:01:44 | 开源项目