QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #713860 | #9536. Athlete Welcome Ceremony | EMTz | WA | 137ms | 519996kb | C++20 | 2.6kb | 2024-11-05 20:44:03 | 2024-11-05 20:44:08 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define lson k<<1
#define rson (k<<1)|1
#define debug cout<<666<<endl;
using namespace std;
const int N=1e6+5;
const int M=1e9+7;
int dp[2][155][155][155][4];
int a[305][305][305];
int sum[305][305][305];
void vision()
{
int n,m;
cin>>n>>m;
string s;
cin>>s;
s=" "+s+" ";
int all=0;
int op=1;
for(int i=1;i<=n;i++)
{
if(s[i]!='?')
{
continue;
}
if(s[i]=='?')all++;
for(int x=0;x<=min((n+1)/2,all);x++)
{
for(int y=0;y<=min((n+1)/2,all-x);y++)
{
int z=all-x-y;
if(z<0) break;
if(z>(n+1)/2) continue;
for(int k=1;k<=3;k++)
{
int la=-1,ne=-1;
if(s[i-1]=='a') la=1;
if(s[i-1]=='b') la=2;
if(s[i-1]=='c') la=3;
if(s[i+1]=='a') ne=1;
if(s[i+1]=='b') ne=2;
if(s[i+1]=='c') ne=3;
if(k==la||k==ne) continue;
if(s[i-1]=='?')
{
for(int j=1;j<=3;j++)
{
if(k==j) continue;
if(k==1&&x>0)dp[op][x][y][z][k]+=dp[op^1][x-1][y][z][j];
if(k==2&&y>0)dp[op][x][y][z][k]+=dp[op^1][x][y-1][z][j];
if(k==3&&z>0)dp[op][x][y][z][k]+=dp[op^1][x][y][z-1][j];
dp[op][x][y][z][k]%=M;
}
}
else
{
if(all==1)
{
if(k==1&&x>0)dp[op][x][y][z][k]=1;
if(k==2&&y>0)dp[op][x][y][z][k]=1;
if(k==3&&z>0)dp[op][x][y][z][k]=1;
continue;
}
for(int j=1;j<=3;j++)
{
if(k==1&&x>0)dp[op][x][y][z][k]+=dp[op^1][x-1][y][z][j];
if(k==2&&y>0)dp[op][x][y][z][k]+=dp[op^1][x][y-1][z][j];
if(k==3&&z>0)dp[op][x][y][z][k]+=dp[op^1][x][y][z-1][j];
dp[op][x][y][z][k]%=M;
}
}
}
}
}
op^=1;
}
for(int i=0;i<=300;i++)
{
for(int j=0;j<=300;j++)
{
for(int z=0;z<=300;z++)
{
if(i+j+z!=all||i>(n+1)/2||j>(n+1)/2||z>(n+1)/2) a[i+1][j+1][z+1]=0;
else
{
a[i+1][j+1][z+1]=dp[op^1][i][j][z][1]+dp[op^1][i][j][z][2]+dp[op^1][i][j][z][3];
a[i+1][j+1][z+1]%=M;
}
sum[i+1][j+1][z+1]=a[i+1][j+1][z+1]+sum[i+1][j+1][z-1+1]+sum[i+1][j-1+1][z+1]-sum[i+1][j-1+1][z-1+1]+sum[i-1+1][j+1][z+1]-sum[i-1+1][j+1][z-1+1]-sum[i-1+1][j-1+1][z+1]+sum[i-1+1][j-1+1][z-1+1];
sum[i+1][j+1][z+1]%=M;
}
}
}
// cout<<a[1][1][1]<<"\n";
while(m--)
{
int x,y,z;
cin>>x>>y>>z;
if(x+y+z<all)
{
cout<<0<<"\n";
continue;
}
int ans=sum[x+1][y+1][z+1];
ans%=M;
cout<<ans<<"\n";
}
return ;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
vision();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 123ms
memory: 447896kb
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: 132ms
memory: 448336kb
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: 127ms
memory: 445920kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 135ms
memory: 447764kb
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: 130ms
memory: 451408kb
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: 127ms
memory: 445656kb
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: 132ms
memory: 479740kb
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: 137ms
memory: 453384kb
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: 128ms
memory: 519996kb
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 -856010171 -880338078 -292135540 10104 219100551 -520715304 -235781478 -96153776 -340305459 204287063 -894079505 191779504 182802705 -784561396 -61307689 797581204 903917420 -106004179 287222624 -421304178 95654849 -542189581 -290650212 85961844 -76669513 783007506 -888880289 295402274 241...
result:
wrong answer 2nd lines differ - expected: '143989836', found: '-856010171'