QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #769360 | #9536. Athlete Welcome Ceremony | KOH-# | WA | 1ms | 5888kb | C++14 | 2.4kb | 2024-11-21 17:19:15 | 2024-11-21 17:19:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)) f|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;return;
}
template <typename T>
inline void print(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10^48);return;
}
#define ll long long
const int N=305,mod=1e9+7;
char a[N];
int b[3][N][N][2];
int c[N][N];
int n, q,cnt,o;
int main(){
scanf("%d%d",&n,&q);
scanf("%s",a+1);
o=0;
if(a[1]=='?'){
cnt++;
b[0][1][0][0]=1;
b[1][0][1][0]=1;
b[2][0][0][0]=1;
}
else{
b[a[1]-'a'][0][0][0]=1;
}
for(int i=2;i<=n;i++){
if(a[i]=='?') cnt++;
for(int j=0;j<=cnt;j++){
for(int k=0;j+k<=cnt;k++){
if(a[i]=='?'){
if(j>0) b[0][j][k][o^1]=(b[1][j-1][k][o]+b[2][j-1][k][o])%mod;
else b[0][j][k][o^1]=0;
if(k>0) b[1][j][k][o^1]=(b[0][j][k-1][o]+b[2][j][k-1][o])%mod;
else b[1][j][k][o^1]=0;
b[2][j][k][o^1]=(b[0][j][k][o]+b[1][j][k][o])%mod;
}
if(a[i]=='a') b[0][j][k][o^1]=(b[1][j][k][o]+b[2][j][k][o])%mod,b[1][j][k][o^1]=b[2][j][k][o^1]=0;
if(a[i]=='b') b[1][j][k][o^1]=(b[0][j][k][o]+b[2][j][k][o])%mod,b[0][j][k][o^1]=b[2][j][k][o^1]=0;
if(a[i]=='c') b[2][j][k][o^1]=(b[0][j][k][o]+b[1][j][k][o])%mod,b[0][j][k][o^1]=b[1][j][k][o^1]=0;
}
}
o^=1;
}
for(int j=0;j<=cnt;j++){
for(int k=0;j+k<=cnt;k++){
c[j][k]=(b[0][j][k][o]+b[1][j][k][o]+b[2][j][k][o])%mod;
if(k>0)c[j][k]=(c[j][k]+c[j][k-1])%mod;
}
}
for(int i=1;i<=q;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
long long ans=0;
for(int j=0;j<=min(x,cnt);j++){
for(int k=0;j+k<=cnt;k++){
if(j+k+z<cnt) continue;
if(k>y) continue;
//printf("%d %d %d %d %d %d\n",j,k,cnt-j-k,b[0][j][k][o],b[1][j][k][o],b[2][j][k][o]);
}
int l=max(0,cnt-j-z),r=min(y,cnt-j);
if(l>r) continue;
ans=(ans+c[j][r])%mod;
if(l>0) ans=(ans+mod-c[j][l-1])%mod;
}
printf("%lld\n",ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3908kb
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: 3844kb
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: 3800kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3896kb
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: 0ms
memory: 3828kb
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: 0
Accepted
time: 0ms
memory: 5888kb
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:
8 8 8 0 8 8 6 8 8 8 8 0 0 0 1 8 4 8 8 8 2 4 1 8 1 6 0 2 8 6 8 8 1 4 2 8 8 0 0 8 2 0 8 8 8 4 8 8 8 8 2 0 0 4 8 8 1 8 7 6 7 0 8 8 8 0 4 7 8 4 0 8 0 4 8 8 8 7 8 4 7 2 8 8 8 0 2 2 8 8 8 4 4 0 8 0 8 8 1 1
result:
ok 100 lines
Test #7:
score: 0
Accepted
time: 1ms
memory: 4120kb
input:
50 100 b????????bca?????c?b??ca?acac?b?b???ca?ab???a?a??? 35 43 36 12 49 47 7 11 34 38 44 22 42 17 10 49 8 38 18 26 44 6 18 14 28 29 6 48 32 47 29 15 48 1 5 33 24 17 18 10 27 32 19 10 34 2 23 9 14 24 39 46 12 34 9 49 26 21 8 46 43 43 3 31 16 2 8 27 7 24 41 35 17 25 31 0 13 47 24 31 23 33 40 30 36 39...
output:
34272000 31599360 497244 34272000 17637520 12290752 34272000 93044 415832 34272000 34272000 0 34272000 16360704 27933952 0 34272000 33886976 7896832 12290752 718 24 0 34272000 34272000 0 34272000 34272000 34272000 32254720 0 5666944 34256640 34272000 34272000 12290752 30493248 34256640 20630016 0 10...
result:
ok 100 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
100 1000 c?cbababcabacbacbacacbacabcbabababacababcbcab?cbabacbacbcbcacbab?bcabcbcababcacbabacbcb?babcbab?baca 13 11 4 4 17 20 14 5 2 16 14 15 8 12 17 19 5 11 5 17 12 20 7 6 19 10 1 6 5 0 13 1 9 7 17 1 20 4 16 11 12 18 19 2 16 18 1 11 19 16 3 7 1 0 6 9 16 6 9 16 6 20 7 0 16 20 1 2 8 16 5 20 18 14 18 ...
output:
16 15 14 16 16 16 16 16 8 2 16 8 16 16 16 16 16 2 16 16 16 0 1 16 16 5 1 5 16 16 16 16 16 15 16 13 16 15 2 16 16 1 8 16 16 16 15 0 16 15 16 16 16 16 8 8 16 16 16 16 16 16 8 16 16 1 8 8 16 16 1 16 1 0 16 2 2 16 7 16 16 8 16 16 16 16 1 16 14 16 16 16 16 5 16 16 14 16 11 16 15 11 2 1 8 16 16 7 16 5 16 ...
result:
ok 1000 lines
Test #9:
score: -100
Wrong Answer
time: 1ms
memory: 4592kb
input:
100 1000 ?????c??????????????????????????b???a????a?????????????????????????c???????????????????????????????? 43 38 20 27 40 32 39 27 33 28 50 43 50 3 46 38 46 14 42 48 10 45 25 28 49 10 49 38 17 42 41 49 22 41 18 44 46 47 25 17 44 35 34 43 22 47 42 32 32 44 40 36 41 24 45 38 45 49 44 18 42 34 32 43...
output:
195508388 259088039 939792871 858846490 10104 334198754 479284703 174283993 18944427 659694548 894876281 515985973 342761527 182802705 215438611 24903472 898235886 313982884 440599794 337549965 39088634 527160619 688006832 529480730 906092786 448494161 718236644 816152457 705467745 176823209 6667784...
result:
wrong answer 1st lines differ - expected: '490475656', found: '195508388'