QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #769066 | #9536. Athlete Welcome Ceremony | __stick | TL | 605ms | 703188kb | C++20 | 2.0kb | 2024-11-21 15:58:56 | 2024-11-21 15:59:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define double long double
const int MAXN=300+10;
const int mod=1e9+7;
int F[MAXN][MAXN][MAXN][3],g[MAXN][MAXN][MAXN][3];
int sum[MAXN][MAXN][MAXN];
inline void MOD(int&x){x-=mod,x+=x>>31&mod;}
inline int get(int i,int j,int k)
{
if(i<0||j<0||k<0)return 0;
return sum[i][j][k];
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,T;cin>>n>>T;
string s;cin>>s;s=' '+s;
if(s[1]=='?')F[1][0][0][0]=F[0][1][0][1]=F[0][0][1][2]=1;
else F[0][0][0][s[1]-'a']=1;
vector<int>cnt(3);
for(int i=1;i<=n;i++)if(s[i]!='?')cnt[s[i]-'a']++;
int tt=0;
for(int x=1;x<n;x++)
{
if(s[x]=='?')tt++;
memset(g,0,sizeof(g));
for(int i=0;i<=tt;i++)
for(int j=0;j+i<=tt;j++)
for(int k=0;i+j+k<=tt;k++)if(s[x+1]=='?')
{
MOD(g[i+1][j][k][0]+=F[i][j][k][1]),MOD(g[i+1][j][k][0]+=F[i][j][k][2]);
MOD(g[i][j+1][k][1]+=F[i][j][k][0]),MOD(g[i][j+1][k][1]+=F[i][j][k][2]);
MOD(g[i][j][k+1][2]+=F[i][j][k][0]),MOD(g[i][j][k+1][2]+=F[i][j][k][1]);
}
else
{
if(s[x+1]=='a')MOD(g[i][j][k][0]+=F[i][j][k][1]),MOD(g[i][j][k][0]+=F[i][j][k][2]);
else if(s[x+1]=='b')MOD(g[i][j][k][1]+=F[i][j][k][0]),MOD(g[i][j][k][1]+=F[i][j][k][2]);
else if(s[x+1]=='c')MOD(g[i][j][k][2]+=F[i][j][k][0]),MOD(g[i][j][k][2]+=F[i][j][k][1]);
}
memcpy(F,g,sizeof(F));
}
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
for(int k=0;k<=n;k++)
{
for(int x=0;x<3;x++)MOD(sum[i][j][k]+=F[i][j][k][x]);
MOD(sum[i][j][k]+=mod-get(i-1,j-1,k));
MOD(sum[i][j][k]+=mod-get(i-1,j,k-1));
MOD(sum[i][j][k]+=mod-get(i,j-1,k-1));
MOD(sum[i][j][k]+=get(i-1,j,k));
MOD(sum[i][j][k]+=get(i,j,k-1));
MOD(sum[i][j][k]+=get(i,j-1,k));
MOD(sum[i][j][k]+=get(i-1,j-1,k-1));
}
while(T--)
{
int x,y,z;cin>>x>>y>>z;
x=min(x,n),y=min(y,n),z=min(z,n);
cout<<sum[x][y][z]<<'\n';
}
return 0;
}
/*
6 1
a?b??c
2 2 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 349ms
memory: 702584kb
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: 349ms
memory: 702740kb
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: 5580kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 605ms
memory: 702064kb
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: 557ms
memory: 703188kb
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
Time Limit Exceeded
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...