QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #713594 | #9536. Athlete Welcome Ceremony | xuxuxuxuxu# | WA | 165ms | 111196kb | C++14 | 3.6kb | 2024-11-05 19:57:00 | 2024-11-05 19:57:00 |
Judging History
answer
#include<cstdio>
#define reg
#define mod 1000000007
// #define meow(args...) fprintf(stderr,args)
int n,q,pos,f[2][302][302][4],g[302][302][302];
int cnta=0,cntb=0,cntc=0;
char s[302];
int main()
{
scanf("%d%d",&n,&q);
scanf("%s",s+1);
// meow("%d %d\n",n,q);
for(reg int i=1;i<=n;++i)
{
if(s[i]=='a') ++cnta;
else if(s[i]=='b') ++cntb;
else if(s[i]=='c') ++cntc;
}
if(s[1]=='?')
{
f[0][0][0][0]=f[0][1][0][1]=f[0][0][1][2]=1;
}
else if(s[1]=='a')
{
f[0][0][0][0]=1;
}
else if(s[1]=='b')
{
f[0][1][0][1]=1;
}
else
{
f[0][0][1][2]=1;
}
pos=0;
for(reg int i=2;i<=n;++i)
{
for(reg int j=0;j<=i;++j)
{
for(reg int k=0;k<=i;++k)
{
for(reg int l=0;l<=2;++l)
{
f[pos^1][j][k][l]=0;
}
}
}
for(reg int j=0;j<=i;++j)
{
for(reg int k=0;k<=i;++k)
{
if(s[i]=='?')
{
f[pos^1][j][k][0]=((f[pos^1][j][k][0]+f[pos][j][k][1])%mod+f[pos][j][k][2])%mod;
f[pos^1][j+1][k][1]=((f[pos^1][j+1][k][1]+f[pos][j][k][0])%mod+f[pos][j][k][2])%mod;
f[pos^1][j][k+1][2]=((f[pos^1][j][k+1][2]+f[pos][j][k][0])%mod+f[pos][j][k][1])%mod;
}
else
{
if(s[i]=='a')
{
f[pos^1][j][k][0]=((f[pos^1][j][k][0]+f[pos][j][k][1])%mod+f[pos][j][k][2])%mod;
}
else if(s[i]=='b')
{
f[pos^1][j+1][k][1]=((f[pos^1][j+1][k][1]+f[pos][j][k][0])%mod+f[pos][j][k][2])%mod;
}
else
{
f[pos^1][j][k+1][2]=((f[pos^1][j][k+1][2]+f[pos][j][k][0])%mod+f[pos][j][k][1])%mod;
}
}
}
}
pos^=1;
// meow("i:%d\n",i);
// for(reg int j=0;j<=i;++j)
// {
// for(reg int k=0;k<=i;++k)
// {
// for(reg int l=0;l<=2;++l)
// meow("f %d %d %d: %d \n",j,k,l,f[pos][j][k][l]);
// }
// }
}
for(reg int j=0;j<=n;++j)
{
for(reg int k=0;k<=n;++k)
{
if(n-j-k<0) continue;
if(s[n]=='a'||s[n]=='?')
{
g[n-j-k][j][k]=f[pos][j][k][0];
}
if(s[n]=='b'||s[n]=='?')
{
g[n-j-k][j][k]=(g[n-j-k][j][k]+f[pos][j][k][1])%mod;
}
if(s[n]=='c'||s[n]=='?')
{
g[n-j-k][j][k]=(g[n-j-k][j][k]+f[pos][j][k][2])%mod;
}
}
}
for(int i=1;i<=300;i++)
for(int j=0;j<=300;j++)
for(int k=0;k<=300;k++)
g[i][j][k]=(g[i][j][k]+g[i-1][j][k])%mod;
for(int i=0;i<=300;i++)
for(int j=1;j<=300;j++)
for(int k=0;k<=300;k++)
g[i][j][k]=(g[i][j][k]+g[i][j-1][k])%mod;
for(int i=0;i<=300;i++)
for(int j=0;j<=300;j++)
for(int k=1;k<=300;k++)
g[i][j][k]=(g[i][j][k]+g[i][j][k-1])%mod;
for(reg int i=1,a,b,c;i<=q;++i)
{
scanf("%d%d%d",&a,&b,&c);
a+=cnta;
b+=cntb;
c+=cntb;
printf("%d\n",g[a][b][c]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 145ms
memory: 110184kb
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: 154ms
memory: 111196kb
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: 147ms
memory: 110672kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Wrong Answer
time: 165ms
memory: 110352kb
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 0 1 0 1
result:
wrong answer 7th lines differ - expected: '1', found: '0'