QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #769196 | #9536. Athlete Welcome Ceremony | __stick | TL | 49ms | 152632kb | C++20 | 2.2kb | 2024-11-21 16:34:06 | 2024-11-21 16:34:13 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const int MAXN=300+10;
const int mod=1e9+7;
int F[MAXN][MAXN][MAXN][3],g[MAXN][MAXN][MAXN][3];
int sum[MAXN][MAXN][MAXN];
inline void MOD(int&x){x-=mod,x+=x>>31&mod;}
inline int get(int i,int j,int k)
{
if(i<0||j<0||k<0)return 0;
return sum[i][j][k];
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,T;cin>>n>>T;
string s;cin>>s;s=' '+s;
if(s[1]=='?')F[1][0][0][0]=F[0][1][0][1]=F[0][0][1][2]=1;
else F[0][0][0][s[1]-'a']=1;
vector<int>cnt(3);
for(int i=1;i<=n;i++)if(s[i]!='?')cnt[s[i]-'a']++;
int tt=0;
int tot=0;
for(int x=1;x<n;x++)
{
tt=x;
for(int i=0;i<=tt;i++)
for(int j=0;i+j<=tt;j++)
for(int k=0;i+j+k<=tt;k++)
g[i][j][k][0]=g[i][j][k][1]=g[i][j][k][2]=0;
for(int i=0;i<=tt;i++)
for(int j=0;j+i<=tt;j++)
for(int k=0;i+j+k<=tt;k++)if(s[x+1]=='?')
{
tot++ ;
MOD(g[i+1][j][k][0]+=F[i][j][k][1]),MOD(g[i+1][j][k][0]+=F[i][j][k][2]);
MOD(g[i][j+1][k][1]+=F[i][j][k][0]),MOD(g[i][j+1][k][1]+=F[i][j][k][2]);
MOD(g[i][j][k+1][2]+=F[i][j][k][0]),MOD(g[i][j][k+1][2]+=F[i][j][k][1]);
}
else
{
tot++;
if(s[x+1]=='a')MOD(g[i][j][k][0]+=F[i][j][k][1]),MOD(g[i][j][k][0]+=F[i][j][k][2]);
else if(s[x+1]=='b')MOD(g[i][j][k][1]+=F[i][j][k][0]),MOD(g[i][j][k][1]+=F[i][j][k][2]);
else if(s[x+1]=='c')MOD(g[i][j][k][2]+=F[i][j][k][0]),MOD(g[i][j][k][2]+=F[i][j][k][1]);
}
for(int i=0;i<=tt+1;i++)
for(int j=0;i+j<=tt+1;j++)
for(int k=0;i+j+k<=tt+1;k++)
memcpy(F[i][j][k],g[i][j][k],sizeof(F[i][j][k]));
}
// cerr<<tot<<'\n';
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
for(int k=0;k<=n;k++)
{
for(int x=0;x<3;x++)MOD(sum[i][j][k]+=F[i][j][k][x]);
MOD(sum[i][j][k]+=mod-get(i-1,j-1,k));
MOD(sum[i][j][k]+=mod-get(i-1,j,k-1));
MOD(sum[i][j][k]+=mod-get(i,j-1,k-1));
MOD(sum[i][j][k]+=get(i-1,j,k));
MOD(sum[i][j][k]+=get(i,j,k-1));
MOD(sum[i][j][k]+=get(i,j-1,k));
MOD(sum[i][j][k]+=get(i-1,j-1,k-1));
}
while(T--)
{
int x,y,z;cin>>x>>y>>z;
x=min(x,n),y=min(y,n),z=min(z,n);
cout<<sum[x][y][z]<<'\n';
}
return 0;
}
/*
6 1
a?b??c
2 2 2
*/
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 11896kb
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: 13980kb
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: 7656kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 0ms
memory: 16448kb
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: 20224kb
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: 3ms
memory: 72416kb
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: 7ms
memory: 72872kb
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: 34ms
memory: 152632kb
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: 0
Accepted
time: 49ms
memory: 151504kb
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:
490475656 143989836 119661929 707864467 10104 219100551 479284703 764218529 903846231 659694548 204287063 105920502 191779504 182802705 215438611 938692318 797581204 903917420 893995828 287222624 578695829 95654849 457810426 709349795 85961844 923330494 783007506 111119718 295402274 241594071 551680...
result:
ok 1000 lines
Test #10:
score: 0
Accepted
time: 37ms
memory: 151620kb
input:
100 1000 c???cacacbcab?cb?acb???ac?bab?bcbcbc?c?bcbcaba??b?ba?c?aca?a?bac?cbcbcba??ca?b????ac?baba?ab?cba?c?c 99 70 32 52 98 84 12 78 77 84 8 87 16 36 0 48 70 100 25 4 15 95 54 35 33 35 90 20 4 69 6 11 76 27 96 48 16 24 18 99 48 1 43 54 35 9 81 75 27 58 52 50 94 14 29 67 27 59 68 53 42 31 46 12 90 2...
output:
380160 380160 226896 64156 0 380160 92 380160 380160 92 0 380160 379648 0 380160 22500 380160 380160 380160 380160 380160 226896 380160 380160 226896 0 380160 380160 380160 380160 152672 380160 5624 226896 380160 380160 379648 0 380160 380160 366848 380160 226896 380160 92 374912 5624 380160 380160 ...
result:
ok 1000 lines
Test #11:
score: -100
Time Limit Exceeded
input:
300 100000 abcacacbabacbcababcacacb?babacbcbacbcababcbcbabcacbcbacacabacacacbacbcbcacbabacbcbcbabcacbababcabcabcabababacbcacbacabcbacbacacacbababababacbcababcbcacacbcbabacabcabababcabacbcbcbabcabacbabacacbcbcacacacbcabcbabcbcabababababcacabcabababcbcbcbcbcabacbabacbabcacbcababacacbcbababababcacacaba...