QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #702790 | #9536. Athlete Welcome Ceremony | ucup-team1338# | WA | 3ms | 24000kb | C++20 | 3.2kb | 2024-11-02 16:34:57 | 2024-11-02 16:35:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define maxn 305
ll dp[maxn][maxn][maxn][3];
ll w1[maxn][maxn][maxn];
int lim[maxn];
int main()
{
int n, q;
string s;
cin >> n >> q >> s;
s = '?' + s;
for (int i = 1; i <= n; i++)
{
if (s[i] == '?')
lim[i] = lim[i - 1] + 1;
else
lim[i] = lim[i - 1];
}
// dp[0][0][0][1]=dp[0][0][0][2]=dp[0][0][0][0]=1;
for (int i = 1; i <= n; i++)
{
if (s[i] == 'a')
{
for (int j = 0; j <= lim[i]; j++)
{
for (int k = 0; (k + j) <= lim[i]; k++)
{
// add 'a'
if (i == 1)
{
dp[i][j][k][0] = 1;
}
else
dp[i][j][k][0] = (dp[i - 1][j][k][1] + dp[i - 1][j][k][2])%mod;
}
}
}
else if (s[i] == 'b')
{
for (int j = 0; j <= lim[i]; j++)
{
for (int k = 0; (k + j) <= lim[i]; k++)
{
// add 'b'
if (i == 1)
dp[i][j][k][1] = 1;
else
dp[i][j][k][1] = (dp[i - 1][j][k][0] + dp[i - 1][j][k][2])%mod;
}
}
}
else if (s[i] == 'c')
{
for (int j = 0; j <= lim[i]; j++)
{
for (int k = 0; (k + j) <= lim[i]; k++)
{
// add 'a'
if (i == 1)
dp[i][j][k][2] = 1;
else
dp[i][j][k][2] = (dp[i - 1][j][k][1] + dp[i - 1][j][k][0])%mod;
}
}
}
else
{
if (i == 1)
{
dp[1][1][0][0] = 1;
dp[1][0][1][1] = 1;
dp[1][0][0][2] = 1;
}
else
{
for (int j = 0; j <= lim[i]; j++)
{
for (int k = 0; (k + j) <= lim[i]; k++)
{
// add 'a'
if (i == 1)
{
dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = 1;
}
else
{
if (j)
dp[i][j][k][0] = (dp[i - 1][j - 1][k][1] + dp[i - 1][j - 1][k][2])%mod;
if (k)
dp[i][j][k][1] = (dp[i - 1][j][k - 1][2] + dp[i - 1][j][k - 1][0])%mod;
dp[i][j][k][2] = (dp[i - 1][j][k][1] + dp[i - 1][j][k][0])%mod;
}
}
}
}
}
}
// for(int i=1;i<=n;i++){
// for(int j=0;j<=lim[i];j++){
// for(int k=0;(k+j)<=lim[i];k++){
// cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k][0]<<' '<<dp[i][j][k][1]<<' '<<dp[i][j][k][2]<<'\n';
// }
// }
// }
for(int j=0;j<=lim[n];j++){
for(int k=0;(k+j)<=lim[n];k++){
(w1[j][k][lim[n]-j-k]+=dp[n][j][k][0])%=mod;
(w1[j][k][lim[n]-j-k]+=dp[n][j][k][1])%=mod;
(w1[j][k][lim[n]-j-k]+=dp[n][j][k][2])%=mod;
}
}
// for (int i = 0; i <= lim[n]; i++)
// {
// for (int j = 0; (i + j) <= lim[n]; j++)
// {
// cout << i << ' ' << j << ' ' << lim[n] - i - j << ' ' << w1[i][j][lim[n]-i-j] << '\n';
// }
// }
for(int i=0;i<=lim[n];i++){
for(int j=0;j<=lim[n];j++){
for(int k=0;k<=lim[n];k++){
if(i)
(w1[i][j][k]+=w1[i-1][j][k])%=mod;
}
}
}
for(int i=0;i<=lim[n];i++){
for(int j=0;j<=lim[n];j++){
for(int k=0;k<=lim[n];k++){
if(i)
(w1[j][i][k]+=w1[j][i-1][k])%=mod;
}
}
}
for(int i=0;i<=lim[n];i++){
for(int j=0;j<=lim[n];j++){
for(int k=0;k<=lim[n];k++){
if(i)
(w1[k][j][i]+=w1[k][j][i-1])%=mod;
}
}
}
while (q--)
{
int x,y,z;
cin>>x>>y>>z;
cout<<w1[x][y][z]<<'\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 16192kb
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: 2ms
memory: 16040kb
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: 5624kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 24000kb
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 0 0 1 0 0 0 0 0 0
result:
wrong answer 2nd lines differ - expected: '1', found: '0'