QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #862734 | #9536. Athlete Welcome Ceremony | 2018ljw# | WA | 0ms | 5896kb | C++14 | 1.5kb | 2025-01-19 09:18:49 | 2025-01-19 09:18:49 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<assert.h>
const int mod=1e9+7;
int n;
char s[302];
int dp[301][301][3],tmp[301][301][3];
int sum[301][301][301];
int main(){
int i,j,k,l,q,c=0;
scanf("%d%d",&n,&q);
scanf("%s",s+1);
if(s[1]=='?')dp[0][0][2]=dp[1][0][0]=dp[0][1][1]=1,c++;
else dp[0][0][s[1]-'a']=1;
for(i=2;i<=n;i++){
if(s[i]=='?')c++;
for(j=0;j<=c;j++){
for(k=0;k<=c;k++){
for(l=0;l<=2;l++)tmp[j][k][l]=dp[j][k][l],dp[j][k][l]=0;
}
}
for(j=0;j<=c;j++){
for(k=0;j+k<=c;k++){
int w=(tmp[j][k][0]+tmp[j][k][1])%mod+tmp[j][k][2];
w%=mod;
if(s[i]!='?')dp[j][k][s[i]-'a']=(w-tmp[j][k][s[i]-'a']+mod)%mod;
else{
if(j+k<c)dp[j][k][2]=(tmp[j][k][0]+tmp[j][k][1])%mod;
if(k)dp[j][k][1]=(tmp[j][k-1][0]+tmp[j][k-1][2])%mod;
if(j)dp[j][k][0]=(tmp[j-1][k][1]+tmp[j-1][k][2])%mod;
}
for(l=0;l<=2;l++)assert(dp[j][k][l]>=0);
}
}
}
for(i=0;i<=c;i++){
for(j=0;i+j<=c;j++){
int w=0;
for(l=0;l<=2;l++)w+=dp[i][j][l],w%=mod;
sum[i][j][c-i-j]=w;
}
}
for(i=0;i<=c;i++){
for(j=0;j<=c;j++){
for(k=1;k<=c;k++)sum[i][j][k]+=sum[i][j][k-1],sum[i][j][k]%=mod;
if(j)for(k=0;k<=c;k++)sum[i][j][k]+=sum[i][j-1][k],sum[i][j][k]%=mod;
}
if(!i)continue;
for(j=0;j<=c;j++){
for(k=0;k<=c;k++)sum[i][j][k]+=sum[i-1][j][k],sum[i][j][k]%=mod;
}
}
for(i=0;i<=c;i++)for(j=0;j<=c;j++)for(k=0;k<=c;k++)assert(sum[i][j][k]>=0);
while(q--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
printf("%d\n",sum[x][y][z]);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
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: 5896kb
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: 1664kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3812kb
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 0 0 1 0 0 0 0 0 0
result:
wrong answer 2nd lines differ - expected: '1', found: '0'