QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#718037#9536. Athlete Welcome CeremonyeastcloudWA 2ms26132kbC++204.8kb2024-11-06 19:33:292024-11-06 19:33:29

Judging History

This is the latest submission verdict.

  • [2024-11-06 19:33:29]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 26132kb
Show
  • [2024-11-06 19:33:29]
  • Submitted

answer


#include<bits/stdc++.h>

#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array
#define IL inline

using namespace std;

#define mod 1000000007
#define N 305

IL int pls(int x,int y){return (x+y>=mod?x+y-mod:x+y);}
IL int sub(int x,int y){return (x-y<0?x-y+mod:x-y);}
IL void Add(int &x,int y){x=pls(x,y);}
IL void Dec(int &x,int y){x=sub(x,y);}
IL int mul(int x,int y){return x*1ll*y%mod;}

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(int x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

int X[N][N][3],Y[N][N][3],Z[N][N][3];
int XY[N][N][N][3],YZ[N][N][N][3],XZ[N][N][N][3];
int f[N][3];

char s[N];

int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    #endif

    int n=read(),q=read();
    scanf("%s",s+1);
    if(s[1]=='?'){
        X[1][1][0]=1;X[1][0][1]=1;X[1][0][2]=1;
        Y[1][0][0]=1;Y[1][1][1]=1;Y[1][0][2]=1;
        Z[1][0][0]=1;Z[1][0][1]=1;Z[1][1][2]=1;
        XY[1][1][0][0]=1;XY[1][0][1][1]=1;XY[1][0][0][2]=1;
        XZ[1][1][0][0]=1;XZ[1][0][0][1]=1;XZ[1][0][1][2]=1;
        YZ[1][0][0][0]=1;YZ[1][1][0][1]=1;YZ[1][0][1][2]=1;
        f[1][1]=f[1][2]=f[1][0]=1;
    }
    else{
        int it=(s[1]-'a');f[1][it]=1;
        X[1][0][it]=1;Y[1][0][it]=1;Z[1][0][it]=1;
        XY[1][0][0][it]=1;XZ[1][0][0][it]=1;
        YZ[1][0][0][it]=1;
    }
    for(int i=2;i<=n;i++){
        if(s[i]!='?'){
            int it=s[i]-'a';
            for(int k=0;k<3;k++)if(it!=k)Add(f[i][it],f[i-1][k]);
            for(int l=0;l<=i;l++){
                for(int k=0;k<3;k++){
                    if(it==k)continue;
                    Add(X[i][l][it],X[i-1][l][k]);
                    Add(Y[i][l][it],Y[i-1][l][k]);
                    Add(Z[i][l][it],Z[i-1][l][k]);
                }
                for(int o=0;o<=i;o++){
                    for(int k=0;k<3;k++){
                        if(it==k)continue;
                        Add(XY[i][l][o][it],XY[i-1][l][o][k]);
                        Add(XZ[i][l][o][it],XZ[i-1][l][o][k]);
                        Add(YZ[i][l][o][it],YZ[i-1][l][o][k]);
                    }
                }
            }
        }
        else{
            for(int j=0;j<3;j++)for(int k=0;k<3;k++)if(j!=k)Add(f[i][j],f[i-1][k]);
            for(int l=0;l<=i;l++){
                for(int j=0;j<3;j++){
                    for(int k=0;k<3;k++){
                        if(j==k)continue;
                        Add(X[i][l+(j==0)][j],X[i-1][l][k]);
                        Add(Y[i][l+(j==1)][j],Y[i-1][l][k]);
                        Add(Z[i][l+(j==2)][j],Z[i-1][l][k]);
                    }
                }
                for(int o=0;o<=i;o++){
                    for(int j=0;j<3;j++){
                        for(int k=0;k<3;k++){
                            if(j==k)continue;
                            Add(XY[i][l+(j==0)][o+(j==1)][j],XY[i-1][l][o][k]);
                            Add(XZ[i][l+(j==0)][o+(j==2)][j],XZ[i-1][l][o][k]);
                            Add(YZ[i][l+(j==1)][o+(j==2)][j],YZ[i-1][l][o][k]);
                        }
                    }
                }
            }
        }
    }

    for(int i=n;i>=0;i--)Add(X[n][i][0],X[n][i+1][0]),Add(X[n][i][0],X[n][i][1]),Add(X[n][i][0],X[n][i][2]);
    for(int i=n;i>=0;i--)Add(Y[n][i][0],Y[n][i+1][0]),Add(Y[n][i][0],Y[n][i][1]),Add(Y[n][i][0],Y[n][i][2]);
    for(int i=n;i>=0;i--)Add(Z[n][i][0],Z[n][i+1][0]),Add(Z[n][i][0],Z[n][i][1]),Add(Z[n][i][0],Z[n][i][2]);

    for(int i=n;i>=0;i--){
        for(int j=n;j>=0;j--){
            Add(XY[n][i][j][0],XY[n][i][j][1]);Add(XY[n][i][j][0],XY[n][i][j][2]);
            Add(XY[n][i][j][0],XY[n][i+1][j][0]);Add(XY[n][i][j][0],XY[n][i][j+1][0]);
            Add(XZ[n][i][j][0],XZ[n][i][j][1]);Add(XZ[n][i][j][0],XZ[n][i][j][2]);
            Add(XZ[n][i][j][0],XZ[n][i+1][j][0]);Add(XZ[n][i][j][0],XZ[n][i][j+1][0]);
            Add(YZ[n][i][j][0],YZ[n][i][j][1]);Add(YZ[n][i][j][0],YZ[n][i][j][2]);
            Add(YZ[n][i][j][0],YZ[n][i+1][j][0]);Add(YZ[n][i][j][0],YZ[n][i][j+1][0]);
        }
    }

    for(int i=1;i<=q;i++){
        int x=read(),y=read(),z=read();
        int res=pls(f[n][0],pls(f[n][1],f[n][2]));
        Dec(res,X[n][x+1][0]);Dec(res,Y[n][y+1][0]);Dec(res,Z[n][z+1][0]);
        Add(res,XY[n][x+1][y+1][0]);Add(res,YZ[n][y+1][z+1][0]);Add(res,XZ[n][x+1][z+1][0]);
        write(res);putchar('\n');
    }

    return 0;

}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 14276kb

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

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

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 2ms
memory: 14512kb

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

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

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
4
8
2
2
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:

wrong answer 39th lines differ - expected: '0', found: '4'
English 繁體中文 简体中文

服务器时间: 2025-02-07 07:43:34 | 开源项目