QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #702987 | #9536. Athlete Welcome Ceremony | ucup-team5318# | WA | 2ms | 8720kb | C++14 | 1.3kb | 2024-11-02 16:54:51 | 2024-11-02 16:54:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=305,mod=1e9+7;
int n,q;
ll f[2][N][N][3],F[N][N];
string a;
void Add(ll&x,ll y){x=(x+y<mod?x+y:x+y-mod);}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifndef ONLINE_JUDGE
assert(freopen(".in","r",stdin));
assert(freopen(".out","w",stdout));
#endif
cin>>n>>q>>a,a=' '+a;
int ct[3]{};
for(int i=1;i<=n;i++)if(a[i]!='?')ct[a[i]-'a']++;
for(int i=0;i<3;i++)f[1][!i][i==1][i]=(a[1]==i+'a'||a[1]=='?');
for(int i=2;i<=n;i++) {
memset(f[i&1],0,sizeof(f[i&1]));
for(int j=0;j<=i;j++)for(int k=0;j+k<=i;k++)
for(int p=0;p<3;p++)if(f[i-1&1][j][k][p]) {
if((a[i]=='?'||a[i]=='a')&&p)Add(f[i&1][j+1][k][0],f[i-1&1][j][k][p]);
if((a[i]=='?'||a[i]=='b')&&p!=1)Add(f[i&1][j][k+1][1],f[i-1&1][j][k][p]);
if((a[i]=='?'||a[i]=='c')&&p!=2)Add(f[i&1][j][k][2],f[i-1&1][j][k][p]);
}
}
for(int i=0;i<=n;i++) {
for(int j=0;j<=n;j++) {
F[i][j]=((j?F[i][j-1]:0)+f[n&1][i][j][0]+f[n&1][i][j][1]+f[n&1][i][j][2])%mod;
}
}
while(q--) {
int A,B,C;cin>>A>>B>>C;
ll ans=0;
A+=ct[0],B+=ct[1],C+=ct[2];
for(int i=0;i<=A;i++)if(B>=n-i-C) {
ans=(ans+F[i][B])%mod;
if(n-i-C>0)ans=(ans+mod-F[i][n-i-C-1])%mod;
}
cout<<(ans+mod)%mod<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8212kb
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: 8004kb
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: 5684kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 2ms
memory: 8720kb
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: 2ms
memory: 8184kb
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'