QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #721375 | #9536. Athlete Welcome Ceremony | qiuqiu | RE | 0ms | 0kb | C++23 | 7.8kb | 2024-11-07 15:58:35 | 2024-11-07 15:58:36 |
Judging History
answer
#include <bits/stdc++.h>
// #define int long long
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int n, q;
int f[303][303][303][3], a[400], b[303];
int pre[303][303][303];
string str;
void solve()
{
cin >> n >> q >> str;
int cnt = 0;
f[0][1][0][0] = f[0][0][1][1] = f[0][0][0][2] = 1;
for(int i = 1; i <= n; i ++)
{
if(str[i - 1] == 'a') a[i] = 0;
else if(str[i - 1] == 'b') a[i] = 1;
else if(str[i - 1] == 'c') a[i] = 2;
else a[i] = 4, b[++ cnt] = i;
}
for(int i = 1; i <= cnt; i ++)
{
if(n == 1) f[i][1][0][0] = f[i][0][1][1] = f[i][0][0][2] = 1;
else if(b[i] == 1)
{
for(int j = 0; j <= 2; j ++)
{
if(j == a[b[i] + 1]) continue;
f[i][j == 0][j == 1][j] = 1;
}
}
else if(b[i] == n)
{
if(a[b[i] - 1] == 4)
{
for(int _i = 0; _i <= i; _i ++)
{
for(int _j = 0; _j + _i <= i; _j ++)
{
for(int now = 0; now <= 2; now ++)
{
for(int la = 0; la <= 2; la ++)
{
if(now == la) continue;
if(now == 0 && _i) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i - 1][_j][la]) % mod;
if(now == 1 && _j) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i][_j - 1][la]) % mod;
if(now == 2 && (i - _i - _j)) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i][_j][la]) % mod;
}
}
}
}
}
else
{
for(int _i = 0; _i <= i; _i ++)
{
for(int _j = 0; _j + _i <= i; _j ++)
{
for(int now = 0; now <= 2; now ++)
{
for(int la = 0; la <= 2; la ++)
{
if(now == a[b[i] - 1]) continue;
if(now == 0 && _i) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i - 1][_j][la]) % mod;
if(now == 1 && _j) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i][_j - 1][la]) % mod;
if(now == 2 && (i - _i - _j)) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i][_j][la]) % mod;
}
}
}
}
}
}
else
{
if(a[b[i] - 1] == 4 && a[b[i] + 1] == 4)
{
for(int _i = 0; _i <= i; _i ++)
{
for(int _j = 0; _j + _i <= i; _j ++)
{
for(int now = 0; now <= 2; now ++)
{
for(int la = 0; la <= 2; la ++)
{
if(now == la) continue;
if(now == 0 && _i) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i - 1][_j][la]) % mod;
if(now == 1 && _j) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i][_j - 1][la]) % mod;
if(now == 2 && (i - _i - _j)) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i][_j][la]) % mod;
}
}
}
}
}
else if(a[b[i] - 1] == 4)
{
for(int _i = 0; _i <= i; _i ++)
{
for(int _j = 0; _j + _i <= i; _j ++)
{
for(int now = 0; now <= 2; now ++)
{
for(int la = 0; la <= 2; la ++)
{
if(now == la || now == a[b[i] + 1]) continue;
if(now == 0 && _i) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i - 1][_j][la]) % mod;
if(now == 1 && _j) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i][_j - 1][la]) % mod;
if(now == 2 && (i - _i - _j)) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i][_j][la]) % mod;
}
}
}
}
}
else if(a[b[i] + 1] == 4)
{
for(int _i = 0; _i <= i; _i ++)
{
for(int _j = 0; _j + _i <= i; _j ++)
{
for(int now = 0; now <= 2; now ++)
{
for(int la = 0; la <= 2; la ++)
{
if(now == a[b[i] - 1]) continue;
if(now == 0 && _i) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i - 1][_j][la]) % mod;
if(now == 1 && _j) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i][_j - 1][la]) % mod;
if(now == 2 && (i - _i - _j)) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i][_j][la]) % mod;
}
}
}
}
}
else
{
for(int _i = 0; _i <= i; _i ++)
{
for(int _j = 0; _j + _i <= i; _j ++)
{
for(int now = 0; now <= 2; now ++)
{
for(int la = 0; la <= 2; la ++)
{
if(now == a[b[i] - 1] || now == a[b[i] + 1]) continue;
if(now == 0 && _i) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i - 1][_j][la]) % mod;
if(now == 1 && _j) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i][_j - 1][la]) % mod;
if(now == 2 && (i - _i - _j)) f[i][_i][_j][now] = (f[i][_i][_j][now] + f[i - 1][_i][_j][la]) % mod;
}
}
}
}
}
}
}
for(int i = 0; i <= cnt; i ++)
{
for(int j = 0; i + j <= cnt; j ++)
{
pre[i][j][cnt - i - j] = ((((f[cnt][i][j][0] + f[cnt][i][j][1]) % mod) + f[cnt][i][j][2]) % mod);
}
}
for(int len = cnt + 1; len <= 900; len ++)
{
for(int i = 0; i <= len && i <= 300; i ++)
{
for(int j = 0; i + j <= len && j <= 300; j ++)
{
int k = len - i - j;
if(k > 300) continue;
pre[i][j][k] = (((((((((((((((((((i ? pre[i - 1][j][k] : 0) + (j ? pre[i][j - 1][k] : 0)) % mod) + (k ? pre[i][j][k - 1] : 0)) % mod) - ((i && j) ? pre[i - 1][j - 1][k] : 0)) % mod) + mod) % mod) - (j && k ? pre[i - 1][j][k - 1] : 0)) % mod) + mod) % mod) - (j && k ? pre[i][j - 1][k - 1] : 0)) % mod) + mod) % mod) + (i && j && k ? pre[i - 1][j - 1][k - 1] : 0)) % mod);
}
}
}
for(int i = 1; i <= q; i ++)
{
int x, y, z;
cin >> x >> y >> z;
cout << pre[x][y][z] << "\n";
}
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _T = 1;
// cin >> _T;
while(_T --)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
6 3 a?b??c 2 2 2 1 1 1 1 0 2