QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #755286 | #9536. Athlete Welcome Ceremony | Stelor | WA | 491ms | 333552kb | C++17 | 4.8kb | 2024-11-16 16:57:18 | 2024-11-16 16:57:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
ll dp[310][310][310][3];
ll pre[310][310][310];
int cnt[3];
void solve(){
int n,q;
cin >> n >> q;
string s;
cin >> s;
s="#"+s;
for(int i=1;i<=n;++i){
if(s[i]=='?') continue;
cnt[s[i]-'a']++;
}
if(s[1]=='a') {
dp[1][1][0][0]=1;
}else if(s[1]=='b'){
dp[1][0][1][1]=1;
}else if(s[1]=='c'){
dp[1][0][0][2]=1;
}else{
dp[1][1][0][0]=1;
dp[1][0][1][1]=1;
dp[1][0][0][2]=1;
}
for(int i=2;i<=n;++i){
for(int j=0;j<=300;++j){
for(int k=0;k<=300;++k){
if(s[i]=='a'&&j>=1){
dp[i][j][k][0]+=dp[i-1][j-1][k][1];
dp[i][j][k][0]%=mod;
dp[i][j][k][0]+=dp[i-1][j-1][k][2];
dp[i][j][k][0]%=mod;
}else if(s[i]=='b'&&k>=1){
dp[i][j][k][1]+=dp[i-1][j][k-1][0];
dp[i][j][k][1]%=mod;
dp[i][j][k][1]+=dp[i-1][j][k-1][2];
dp[i][j][k][1]%=mod;
}else if(s[i]=='c'){
dp[i][j][k][2]+=dp[i-1][j][k][0];
dp[i][j][k][2]%=mod;
dp[i][j][k][2]+=dp[i-1][j][k][1];
dp[i][j][k][2]%=mod;
}else{
if(s[i-1]=='a'){
if(k>=1){
dp[i][j][k][1]+=dp[i-1][j][k-1][0];
dp[i][j][k][1]%=mod;
}
dp[i][j][k][2]+=dp[i-1][j][k][0];
dp[i][j][k][2]%=mod;
}else if(s[i-1]=='b'){
if(j>=1){
dp[i][j][k][0]+=dp[i-1][j-1][k][1];
dp[i][j][k][0]%=mod;
}
dp[i][j][k][2]+=dp[i-1][j][k][1];
dp[i][j][k][2]%=mod;
}else if(s[i-1]=='c'){
if(j>=1){
dp[i][j][k][0]+=dp[i-1][j-1][k][2];
dp[i][j][k][0]%=mod;
}
if(k>=1){
dp[i][j][k][1]+=dp[i-1][j][k-1][2];
dp[i][j][k][1]%=mod;
}
}else{
if(j>=1){
dp[i][j][k][0]+=dp[i-1][j-1][k][1];
dp[i][j][k][0]+=dp[i-1][j-1][k][2];
dp[i][j][k][0]%=mod;
}
if(k>=1){
dp[i][j][k][1]+=dp[i-1][j][k-1][0];
dp[i][j][k][1]+=dp[i-1][j][k-1][2];
dp[i][j][k][1]%=mod;
}
dp[i][j][k][2]+=dp[i-1][j][k][0];
dp[i][j][k][2]+=dp[i-1][j][k][1];
dp[i][j][k][2]%=mod;
}
}
}
}
}
for(int i=0;i<=300;++i){
for(int j=0;j<=300;++j){
for(int k=0;k<=300;++k){
if(i+j+k==n){
pre[i][j][k]+=dp[n][i][j][0];
pre[i][j][k]+=dp[n][i][j][1];
pre[i][j][k]+=dp[n][i][j][2];
pre[i][j][k]%=mod;
}
if(i>=1){
pre[i][j][k]+=pre[i-1][j][k];
pre[i][j][k]%=mod;
}
if(j>=1){
pre[i][j][k]+=pre[i][j-1][k];
pre[i][j][k]%=mod;
}
if(k>=1){
pre[i][j][k]+=pre[i][j][k-1];
pre[i][j][k]%=mod;
}
if(i>=1&&j>=1){
pre[i][j][k]-=pre[i-1][j-1][k];
pre[i][j][k]%=mod;
}
if(i>=1&&k>=1){
pre[i][j][k]-=pre[i-1][j][k-1];
pre[i][j][k]%=mod;
}
if(k>=1&&j>=1){
pre[i][j][k]-=pre[i][j-1][k-1];
}
if(i>=1&&j>=1&&k>=1){
pre[i][j][k]+=pre[i-1][j-1][k-1];
pre[i][j][k]%=mod;
}
}
}
}
while(q--){
int a,b,c;
cin >> a >> b >> c;
a=min({a+cnt[0],n});
b=min({b+cnt[1],n});
c=min({c+cnt[2],n});
cout<<pre[a][b][c]<<'\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t=1;
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 455ms
memory: 237148kb
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: 479ms
memory: 237376kb
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: 471ms
memory: 226144kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 451ms
memory: 246172kb
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: 460ms
memory: 246228kb
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
Wrong Answer
time: 491ms
memory: 333552kb
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...
output:
16 16 14 1 16 16 8 14 16 16 16 0 0 1 4 16 10 16 16 16 2 9 4 14 1 8 0 2 16 8 16 16 1 10 2 14 16 0 0 16 2 0 16 16 16 10 14 16 16 16 2 2 0 9 16 16 4 14 14 8 14 2 16 16 16 2 9 14 16 9 0 16 1 10 16 16 16 14 16 7 14 2 16 16 16 2 2 2 16 14 14 10 9 0 14 0 16 16 4 1
result:
wrong answer 1st lines differ - expected: '8', found: '16'