QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#755286#9536. Athlete Welcome CeremonyStelorWA 491ms333552kbC++174.8kb2024-11-16 16:57:182024-11-16 16:57:18

Judging History

This is the latest submission verdict.

  • [2024-11-16 16:57:18]
  • Judged
  • Verdict: WA
  • Time: 491ms
  • Memory: 333552kb
Show
  • [2024-11-16 16:57:18]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
ll dp[310][310][310][3];
ll pre[310][310][310];
int cnt[3];
void solve(){
    int n,q;
    cin >> n >> q;
    string s;
    cin >> s;
    s="#"+s;
    for(int i=1;i<=n;++i){
        if(s[i]=='?') continue;
        cnt[s[i]-'a']++;
    }
    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;
    }else{
        dp[1][1][0][0]=1;
        dp[1][0][1][1]=1;
        dp[1][0][0][2]=1;
    }
    for(int i=2;i<=n;++i){
        for(int j=0;j<=300;++j){
            for(int k=0;k<=300;++k){
                if(s[i]=='a'&&j>=1){
                    dp[i][j][k][0]+=dp[i-1][j-1][k][1];
                    dp[i][j][k][0]%=mod;
                    dp[i][j][k][0]+=dp[i-1][j-1][k][2];
                    dp[i][j][k][0]%=mod;
                }else if(s[i]=='b'&&k>=1){
                    dp[i][j][k][1]+=dp[i-1][j][k-1][0];
                    dp[i][j][k][1]%=mod;
                    dp[i][j][k][1]+=dp[i-1][j][k-1][2];
                    dp[i][j][k][1]%=mod;
                }else if(s[i]=='c'){
                    dp[i][j][k][2]+=dp[i-1][j][k][0];
                    dp[i][j][k][2]%=mod;
                    dp[i][j][k][2]+=dp[i-1][j][k][1];
                    dp[i][j][k][2]%=mod;
                }else{
                    if(s[i-1]=='a'){
                        if(k>=1){
                            dp[i][j][k][1]+=dp[i-1][j][k-1][0];
                            dp[i][j][k][1]%=mod;

                        }
                        dp[i][j][k][2]+=dp[i-1][j][k][0];
                        dp[i][j][k][2]%=mod;

                    }else if(s[i-1]=='b'){
                        if(j>=1){
                            dp[i][j][k][0]+=dp[i-1][j-1][k][1];
                            dp[i][j][k][0]%=mod;
                        }
                        dp[i][j][k][2]+=dp[i-1][j][k][1];
                        dp[i][j][k][2]%=mod;
                    }else if(s[i-1]=='c'){
                        if(j>=1){
                            dp[i][j][k][0]+=dp[i-1][j-1][k][2];
                            dp[i][j][k][0]%=mod;
                        }
                        if(k>=1){
                            dp[i][j][k][1]+=dp[i-1][j][k-1][2];
                            dp[i][j][k][1]%=mod;
                        }
                    }else{
                        if(j>=1){
                            dp[i][j][k][0]+=dp[i-1][j-1][k][1];
                            dp[i][j][k][0]+=dp[i-1][j-1][k][2];
                            dp[i][j][k][0]%=mod;
                        }
                        if(k>=1){
                            dp[i][j][k][1]+=dp[i-1][j][k-1][0];
                            dp[i][j][k][1]+=dp[i-1][j][k-1][2];
                            dp[i][j][k][1]%=mod;
                        }
                        dp[i][j][k][2]+=dp[i-1][j][k][0];
                        dp[i][j][k][2]+=dp[i-1][j][k][1];
                        dp[i][j][k][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+j+k==n){
                    pre[i][j][k]+=dp[n][i][j][0];
                    pre[i][j][k]+=dp[n][i][j][1];
                    pre[i][j][k]+=dp[n][i][j][2];
                    pre[i][j][k]%=mod;
                }
                if(i>=1){
                    pre[i][j][k]+=pre[i-1][j][k];
                    pre[i][j][k]%=mod;
                }
                if(j>=1){
                    pre[i][j][k]+=pre[i][j-1][k];
                    pre[i][j][k]%=mod;
                }
                if(k>=1){
                    pre[i][j][k]+=pre[i][j][k-1];
                    pre[i][j][k]%=mod;
                }
                if(i>=1&&j>=1){
                    pre[i][j][k]-=pre[i-1][j-1][k];
                    pre[i][j][k]%=mod;
                }
                if(i>=1&&k>=1){
                    pre[i][j][k]-=pre[i-1][j][k-1];
                    pre[i][j][k]%=mod;
                }
                if(k>=1&&j>=1){
                    pre[i][j][k]-=pre[i][j-1][k-1];
                }
                if(i>=1&&j>=1&&k>=1){
                    pre[i][j][k]+=pre[i-1][j-1][k-1];
                    pre[i][j][k]%=mod;
                }
            }
        }
    }
    while(q--){
        int a,b,c;
        cin >> a >> b >> c;
        a=min({a+cnt[0],n});
        b=min({b+cnt[1],n});
        c=min({c+cnt[2],n});
        cout<<pre[a][b][c]<<'\n';
    }  
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    t=1;
    while(t--)solve();
    return 0;
}
源文件, 语言: C++17

详细

Test #1:

score: 100
Accepted
time: 455ms
memory: 237148kb

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

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

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 451ms
memory: 246172kb

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

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: -100
Wrong Answer
time: 491ms
memory: 333552kb

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:

16
16
14
1
16
16
8
14
16
16
16
0
0
1
4
16
10
16
16
16
2
9
4
14
1
8
0
2
16
8
16
16
1
10
2
14
16
0
0
16
2
0
16
16
16
10
14
16
16
16
2
2
0
9
16
16
4
14
14
8
14
2
16
16
16
2
9
14
16
9
0
16
1
10
16
16
16
14
16
7
14
2
16
16
16
2
2
2
16
14
14
10
9
0
14
0
16
16
4
1

result:

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

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