QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#714686 | #9536. Athlete Welcome Ceremony | iwew# | RE | 0ms | 0kb | C++20 | 2.7kb | 2024-11-06 02:25:33 | 2024-11-06 02:25:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 302, mod = 1e9 + 7;
int dp[2][N][N][4];
int f[N][N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
string s;
cin >> n >> q >> s;
vector<int> pre(n, 0);
pre[0] = (s[0] == '?');
for(int i = 1; i < n; i ++ ) {
pre[i] = pre[i - 1] + (s[i] == '?');
}
int cur = 0;
dp[0][0][0][3] = 1;
for(int i = 0; i < n; i ++ ) {
cur ^= 1;
for(int j = 0; j <= pre[i]; j ++ ) {
for(int k = 0; k <= pre[i]; k ++ ) {
for(int l = 0; l < 4; l ++ ) {
dp[cur][j][k][l] = 0;
}
}
}
for(int j = 0; j <= pre[i]; j ++ ) {
for(int k = 0; k <= pre[i]; k ++ ) {
if(j + k > pre[i]) continue;
for(int l = 0; l < 3; l ++ ) {
if(s[i] == '?') {
if(l == 0 && j >= 1) {
for(int u = 0; u < 4; u ++ ) {
if(u != l) {
dp[cur][j][k][l] = (dp[cur][j][k][l] + dp[cur ^ 1][j - 1][k][u]) % mod;
}
}
}
if(l == 1 && k >= 1) {
for(int u = 0; u < 4; u ++ ) {
if(u != l) {
dp[cur][j][k][l] = (dp[cur][j][k][l] + dp[cur ^ 1][j][k - 1][u]) % mod;
}
}
}
if(l == 2 && j + k + 1 <= pre[i]) {
for(int u = 0; u < 4; u ++ ) {
if(u != l) {
dp[cur][j][k][l] = (dp[cur][j][k][l] + dp[cur ^ 1][j][k][u]) % mod;
}
}
}
}
}
}
}
for(int j = 0; j <= pre[i]; j ++ ) {
for(int k = 0; k <= pre[i]; k ++ ) {
if(s[i] != '?') {
int l = s[i] - 'a';
for(int u = 0; u < 4; u ++ ) {
if(u != l) {
dp[cur][j][k][l] = (dp[cur][j][k][l] + dp[cur ^ 1][j][k][u]) % mod;
}
}
}
}
}
}
for(int i = 0; i <= pre[n - 1]; i ++ ) {
for(int j = 0; j <= pre[n - 1]; j ++ ) {
int ca = i, cb = j, cc = pre[n - 1] - ca - cb;
if(cc >= 0) {
for(int k = 0; k < 3; k ++ ) {
f[ca][cb][cc] = (f[ca][cb][cc] + dp[cur][i][j][k]) % mod;
}
}
}
}
for(int i = 0; i <= pre[n - 1]; i ++ ) {
for(int j = 0; j <= pre[n - 1]; j ++ ) {
for(int k = 0; k <= pre[n - 1]; k ++ ) {
f[i][j][k] = (f[i][j][k] + f[i][j][k - 1]) % mod;
}
}
}
for(int i = 0; i <= pre[n - 1]; i ++ ) {
for(int j = 0; j <= pre[n - 1]; j ++ ) {
for(int k = 0; k <= pre[n - 1]; k ++ ) {
f[i][j][k] = (f[i][j][k] + f[i][j - 1][k]) % mod;
}
}
}
for(int i = 0; i <= pre[n - 1]; i ++ ) {
for(int j = 0; j <= pre[n - 1]; j ++ ) {
for(int k = 0; k <= pre[n - 1]; k ++ ) {
f[i][j][k] = (f[i][j][k] + f[i - 1][j][k]) % mod;
}
}
}
while(q -- ) {
int x, y, z;
cin >> x >> y >> z;
cout << f[x][y][z] << '\n';
}
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
6 3 a?b??c 2 2 2 1 1 1 1 0 2