QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #721660 | #9536. Athlete Welcome Ceremony | qiuqiu | WA | 1ms | 5700kb | C++23 | 18.4kb | 2024-11-07 16:33:07 | 2024-11-07 16:33:07 |
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[303], b[303];
int pre[303][303][303];
// int a[N], f[N][4], b[N], d[303][303][303];
string str;
void solve()
{
for(int i = 0; i <= 302; i ++) a[i] = 0;
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] == '?') b[++ cnt] = i;
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;
// cout << j << " " << a[2] << "\n";
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;
}
// cout << f[i][_i][_j][now] << " ";
}
// cout << endl;
}
}
}
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
{
// return;
if(a[b[i] - 1] == 4 && a[b[i] + 1] == 4)
{
// return;
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;
}
// cout << f[i][_i][_j][now] << " ";
}
// cout << endl;
}
}
}
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
{
return;
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 x = 0; x <= i; x ++)
// {
// for(int y = 0; y + x <= i; y ++)
// {
// cout << x << " " << y << " " << i - x - y << " : " << f[i][x][y] << "\n";
// }
// }
}
// for(int len = 1; len <= cnt; len ++)
// {
// for(int i = 0; i <= len; i ++)
// {
// for(int j = 0; j + i <= len; j ++)
// {
// for(int k = 1; k <= 3; k ++)
// {
// cout << i << " " << j << " " << len - i - j << " " << k << " : " << f[len][i][j][k] << "\n";
// }
// }
// }
// }
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";
// cout << f[cnt][x][y][1] + f[cnt][x][y][2] + f[cnt][x][y][3] << "\n";
}
// for(int i = 1; i <= n; i ++)
// {
// if(i == 1)
// {
// if(n == 1)
// {
// if(a[i] == 4)
// {
// f[++ cnt][1][0][1] = 1;
// f[cnt][0][1][2] = 1;
// f[cnt][0][0][3] = 1;
// }
// else if(a[i] == 3) f[i][0][0][3] = 1;
// else if(a[i] == 2) f[i][0][0][2] = 1;
// else if(a[i] == 1) f[i][0][0][1] = 1;
// }
// else
// {
// if(a[i] == 4)
// {
// if(a[i + 1] != 1) f[++ cnt][1][0][1] = 1;
// if(a[i + 1] != 2) f[cnt][0][1][2] = 1;
// if(a[i + 1] != 3) f[cnt][0][0][3] = 1;
// }
// else if(a[i] == 3) f[i][0][0][3] = 1;
// else if(a[i] == 2) f[i][0][0][2] = 1;
// else if(a[i] == 1) f[i][0][0][1] = 1;
// }
// }
// else
// {
// if(a[i] == 4)
// {
// if(i == n)
// {
// ++ cnt;
// for(int j = 0; j <= cnt; j ++)
// {
// for(int k = 0; k + j <= cnt; k ++)
// {
// for(int _j = 1; _j <= 3; _j ++)
// {
// if(j && _j != 1) f[i][j][k][1] = (f[i][j][k][1] + f[i - 1][j - 1][k][_j]) % mod;
// if(k && _j != 3) f[i][j][k][2] = (f[i][j][k][2] + f[i - 1][j][k - 1][_j]) % mod;
// if(cnt - j - k && _j != 3) f[i][j][k][3] = (f[i][j][k][3] + f[i - 1][j][k][_j]) % mod;
// }
// }
// }
// }
// else
// {
// if(a[i + 1] == 4)
// {
// ++ cnt;
// for(int j = 0; j <= cnt; j ++)
// {
// for(int k = 0; k + j <= cnt; k ++)
// {
// for(int _j = 1; _j <= 3; _j ++)
// {
// if(j && _j != 1) f[i][j][k][1] = (f[i][j][k][1] + f[i - 1][j - 1][k][_j]) % mod;
// if(k && _j != 3) f[i][j][k][2] = (f[i][j][k][2] + f[i - 1][j][k - 1][_j]) % mod;
// if(cnt - j - k && _j != 3) f[i][j][k][3] = (f[i][j][k][3] + f[i - 1][j][k][_j]) % mod;
// }
// }
// }
// }
// else
// {
// ++ cnt;
// for(int j = 0; j <= cnt; j ++)
// {
// for(int k = 0; k + j <= cnt; k ++)
// {
// for(int _j = 1; _j <= 3; _j ++)
// {
// if(a[i + 1] != 1 && j && _j != 1) f[i][j][k][1] = (f[i][j][k][1] + f[i - 1][j - 1][k][_j]) % mod;
// if(a[i + 1] != 2 && k && _j != 3) f[i][j][k][2] = (f[i][j][k][2] + f[i - 1][j][k - 1][_j]) % mod;
// if(a[i + 1] != 3 && cnt - j - k && _j != 3) f[i][j][k][3] = (f[i][j][k][3] + f[i - 1][j][k][_j]) % mod;
// }
// }
// }
// }
// }
// }
// else
// {
// for(int j = 0; j <= cnt; j ++)
// {
// for(int k = 0; k + j <= cnt; k ++)
// {
// for(int _i = 1; _i <= 3; _i ++)
// {
// for(int _j = 1; _j <= 3; _j ++)
// {
// if(_i == _j) continue;
// f[i][j][k][_i] = (f[i][j][k][_i] + f[i - 1][j][k][_j]) % mod;
// }
// }
// }
// }
// }
// }
// cout << cnt << " ";
// }
// for(int i = 1; i <= q; i ++)
// {
// int x, y, z;
// cin >> x >> y >> z;
// cout << ((((f[cnt][x][y][1] + f[cnt][x][y][2]) % mod) + f[cnt][x][y][3]) % mod) << "\n";
// }
// f[0][1] = f[0][2] = f[0][3] = 1;
// for(int i = 1; i <= n; i ++)
// {
// if(str[i - 1] == 'a') a[i] = 1;
// else if(str[i - 1] == 'b') a[i] = 2;
// else if(str[i - 1] == 'c') a[i] = 3;
// else a[i] = 4, b[++ cnt] = i;
// }
// for(int i = 1; i <= n; i ++)
// {
// if(i == 1)
// {
// if(a[i] == 4)
// {
// if(n > 1)
// {
// if(a[i + 1] != 1) f[i][1] = 1;
// if(a[i + 1] != 2) f[i][2] = 1;
// if(a[i + 1] != 3) f[i][3] = 1;
// }
// else
// {
// f[i][1] = 1;
// f[i][2] = 1;
// f[i][3] = 1;
// }
// }
// else f[i][a[i]] = 1;
// cout << i << " : " << f[i][1] << " " << f[i][2] << " " << f[i][3] << "\n";
// continue;
// }
// if(a[i] == 4)
// {
// if(i == n)
// {
// f[i][1] = (f[i - 1][2] + f[i - 1][3]) % mod;
// f[i][2] = (f[i - 1][1] + f[i - 1][3]) % mod;
// f[i][3] = (f[i - 1][2] + f[i - 1][1]) % mod;
// }
// else
// {
// if(a[i + 1] == 4)
// {
// f[i][1] = (f[i - 1][2] + f[i - 1][3]) % mod;
// f[i][2] = (f[i - 1][1] + f[i - 1][3]) % mod;
// f[i][3] = (f[i - 1][2] + f[i - 1][1]) % mod;
// }
// else
// {
// if(a[i + 1] != 1) f[i][1] = (f[i - 1][2] + f[i - 1][3]) % mod;
// if(a[i + 1] != 2) f[i][2] = (f[i - 1][1] + f[i - 1][3]) % mod;
// if(a[i + 1] != 3) f[i][3] = (f[i - 1][2] + f[i - 1][1]) % mod;
// }
// }
// }
// else
// {
// if(a[i] == 1) f[i][a[i]] = (f[i - 1][2] + f[i - 1][3]) % mod;
// else if(a[i] == 2) f[i][a[i]] = (f[i - 1][1] + f[i - 1][3]) % mod;
// else if(a[i] == 3) f[i][a[i]] = (f[i - 1][2] + f[i - 1][1]) % mod;
// }
// cout << i << " : " << f[i][1] << " " << f[i][2] << " " << f[i][3] << "\n";
// }
// for(int len = 1; len <= cnt; len ++)
// {
// if(len == 1)
// {
// d[1][0][0] = f[b[len]][1];
// d[0][1][0] = f[b[len]][2];
// d[0][0][1] = f[b[len]][3];
// }
// else
// {
// for(int i = 0; i <= len && i <= cnt; i ++)
// {
// for(int j = 0; j + i <= len && j + i <= cnt; j ++)
// {
// int k = len - i - j;
// if(i && f[b[len]][1] && d[i - 1][j][k]) d[i][j][k] = (f[b[len]][1] + d[i - 1][j][k]) % mod;
// if(j && f[b[len]][2] && d[i][j - 1][k]) d[i][j][k] = (f[b[len]][2] + d[i][j - 1][k]) % mod;
// if(k && f[b[len]][3] && d[i][j][k - 1]) d[i][j][k] = (f[b[len]][3] + d[i][j][k - 1]) % mod;
// cout << i << " " << j << " " << k << " " << d[i][j][k] << "\n";
// }
// }
// }
// }
// for(int len = 1; len <= n * 3; len ++)
// {
// if(len <= cnt)
// {
// for(int i = 0; i <= len && i <= cnt; i ++)
// {
// for(int j = 0; j + i <= len && j + i <= cnt; j ++)
// {
// int k = len - i - j;
// if(k) d[i][j][k] = (f[b[len]][3] + d[i][j][k - 1]) % mod;
// if(j) d[i][j][k] = (f[b[len]][2] + d[i][j - 1][k]) % mod;
// if(i) d[i][j][k] = (f[b[len]][1] + d[i - 1][j][k]) % mod;
// cout << i << " " << j << " " << k << " " << d[i][j][k] << "\n";
// }
// }
// }
// else
// {
// for(int i = 0; i <= len && i <= 300; i ++)
// {
// for(int j = 0; j + i <= len && j <= 300; j ++)
// {
// int k = len - i - j;
// if(k) d[i][j][k] = (d[i][j][k] + d[i][j][k - 1]) % mod;
// if(j) d[i][j][k] = (d[i][j][k] + d[i][j - 1][k]) % mod;
// if(i) d[i][j][k] = (d[i][j][k] + d[i - 1][j][k]) % mod;
// }
// }
// }
// }
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _T = 1;
// cin >> _T;
while(_T --)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5700kb
input:
6 3 a?b??c 2 2 2 1 1 1 1 0 2
output:
result:
wrong answer 1st lines differ - expected: '3', found: ''