QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #772380 | #9536. Athlete Welcome Ceremony | ZycK# | WA | 1ms | 6028kb | C++14 | 2.6kb | 2024-11-22 19:09:12 | 2024-11-22 19:09:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn=344;
typedef long long ll;
char s[maxn];
int num[maxn];
int cnt[maxn][3];
int f[2][maxn][maxn][3];
int n,Q;
int tmp[4];
ll sum[304][304];
const int mod=1e9+7;
int main()
{
scanf("%d%d",&n,&Q);
scanf("%s",s+1);
int cur=1;
if(s[1]=='?')
{
f[1][1][0][0]=1;
f[1][0][1][1]=1;
f[1][0][0][2]=1;
}else if(s[1]=='a')
f[1][1][0][0]=1;
else if(s[1]=='b')
f[1][0][1][1]=1;
else if(s[1]=='c')
f[1][0][0][2]=1;
for(int i=1;i<=n;i++)
{
for(int t=0;t<=2;t++)
{
cnt[i][t]=cnt[i-1][t];
if(s[i]-'a'==t)
cnt[i][t]++;
}
num[i]=num[i-1]+(s[i]=='?');
}
for(int i=2;i<=n;i++)
{
for(int j=0;j<=n;j++)
for(int k=0;k<=n;k++)
for(int l=0;l<=2;l++)
f[i&1][j][k][l]=0;
for(int j=0;j<=i;j++)
{
for(int k=0;k<=i;k++)
{
if(j+k>i) continue;
tmp[0]=j; tmp[1]=k; tmp[2]=i-j-k;
for(int l=0;l<=2;l++)
{
f[i&1][j][k][l]=0;
if((s[i]=='?'||s[i]-'a'==l)&&tmp[l])
{
for(int t=0;t<=2;t++)
{
if(t==l) continue;
if(l==0) f[i&1][j][k][l]+=f[!(i&1)][j-1][k][t];
else if(l==1) f[i&1][j][k][l]+=f[!(i&1)][j][k-1][t];
else f[i&1][j][k][l]+=f[!(i&1)][j][k][t];
f[i&1][j][k][l]%=mod;
}
}
// if(f[i&1][j][k][l]) cerr<<i<<" "<<j<<" "<<k<<" "<<l<<" "<<f[i&1][j][k][l]<<endl;
}
}
}
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
for(int t=0;t<=2;t++)
sum[i][j]=(sum[i][j]+f[n&1][i][j][t])%mod;
if(j) sum[i][j]=(sum[i][j]+sum[i][j-1])%mod;
}
}
while(Q--)
{
int x,y,z; cin>>x>>y>>z;
x+=min(cnt[n][0],n); y+=min(cnt[n][1],n); z=n-(cnt[n][2]+z);
// cerr<<x<<" "<<y<<" "<<z<<endl;
ll ans=0;
for(int i=0;i<=x;i++)
{
if(z-i<=y)
ans=(ans+sum[i][y]-((z-i>0&&z-i>=y)?sum[i][z-i-1]:0)+mod)%mod;
// cerr<<ans<<endl;
}
printf("%lld\n",ans);
}
}
/*
6 3
a?b??c
2 2 2
1 1 1
1 0 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3996kb
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: 3940kb
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: 1ms
memory: 5984kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 1ms
memory: 6000kb
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: -100
Wrong Answer
time: 1ms
memory: 6028kb
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 0 5 11 0
result:
wrong answer 7th lines differ - expected: '16', found: '0'