QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #747475 | #9536. Athlete Welcome Ceremony | ucup-team1412 | WA | 0ms | 24416kb | C++23 | 4.5kb | 2024-11-14 17:16:54 | 2024-11-14 17:16:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const ll p = 1e9 + 7;
const ll MAXN = 300;
ll dp[MAXN][MAXN][MAXN][4];
ll g[MAXN][MAXN][MAXN];
ll n, t, q;
string c;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
cin >> c;
string s = "0" + c;
ll cnt = 0;
ll cnta = 0, cntb = 0, cntc = 0;
for (ll i = 1; i <= n; i++) {
if (s[i] == '?') cnt++;
if (s[i] == 'a') cnta++;
if (s[i] == 'b') cntb++;
if (s[i] == 'c') cntc++;
if (i == 1) {
if (s[i] == 'a') {
dp[1][0][0][1] = 1;
}
else if (s[i] == 'b') {
dp[0][1][0][2] = 1;
}
else if (s[i] == 'c') {
dp[0][0][1][3] = 1;
}
else {
dp[1][0][0][1] = 1;
dp[0][1][0][2] = 1;
dp[0][0][1][3] = 1;
}
}
else {
for (ll a = 0; a <= i; a++) {
for (ll b = 0; a + b <= i; b++) {
if (s[i] == 'a') {
if (a != 0) {
dp[a][b][i - a - b][1] = dp[a - 1][b][i - a - b][2] + dp[a - 1][b][i - a - b][3];
dp[a][b][i - a - b][1] %= p;
}
}
else if (s[i] == 'b') {
if (b != 0) {
dp[a][b][i - a - b][2] = dp[a][b - 1][i - a - b][1] + dp[a][b - 1][i - a - b][3];
dp[a][b][i - a - b][2] %= p;
}
}
else if (s[i] == 'c') {
if (i - a - b != 0) {
dp[a][b][i - a - b][3] = dp[a][b][i - a - b - 1][1] + dp[a][b][i - a - b - 1][2];
dp[a][b][i - a - b][3] %= p;
}
}
else {
if (a != 0) {
dp[a][b][i - a - b][1] = dp[a - 1][b][i - a - b][2] + dp[a - 1][b][i - a - b][3];
dp[a][b][i - a - b][1] %= p;
}
if (b != 0) {
dp[a][b][i - a - b][2] = dp[a][b - 1][i - a - b][1] + dp[a][b - 1][i - a - b][3];
dp[a][b][i - a - b][2] %= p;
}
if (i - a - b != 0) {
dp[a][b][i - a - b][3] = dp[a][b][i - a - b - 1][1] + dp[a][b][i - a - b - 1][2];
dp[a][b][i - a - b][3] %= p;
}
}
}
}
}
}
// cout << dp[1][1][1][1] + dp[1][1][1][2] + dp[1][1][1][3];
// for (ll x = 1; x <= n + 1; x++) {
// for (ll y = 1; y <= n + 1; y++) {
// for (ll z = 1; z <= n + 1; z++) {
// if (x + y + z > n + 3) break;
// g[x][y][z] = g[x - 1][y][z] + g[x][y - 1][z] + g[x][y][z - 1] - g[x][y - 1][z - 1] - g[x - 1][y][z - 1] - g[x - 1][y - 1][z] + g[x - 1][y - 1][z - 1];
// g[x][y][z] %= p;
// if (x + y + z == n + 3) {
// g[x][y][z] += (dp[x][y][z][1] + dp[x][y][z][2] + dp[x][y][z][3]) % p;
// g[x][y][z] %= p;
// }
// }
// }
// }
// for (ll i = 0; i <= n; i++) {
// for (ll j = 0; j <= n; j++) {
// for (ll k = 1; k <= 3; k++) {
// g[i+1][j+1][n-i-j+1]+=dp[]
// }
// }
// }
for (ll i = 1; i <= n + 1; i++) {
for (ll j = 1; j <= n + 1; j++) {
for (ll k = 1; k <= n + 1; k++) {
g[i][j][k] = g[i - 1][j][k] + g[i][j - 1][k] + g[i][j][k - 1] - g[i - 1][j - 1][k] - g[i - 1][j][k - 1] - g[i][j - 1][k - 1] + g[i - 1][j - 1][k - 1];
g[i][j][k] %= p;
if (i + j + k == n + 3) {
ll now = 0;
for (ll t = 1; t <= 3; t++) {
now += dp[i - 1][j - 1][k - 1][t];
}
g[i][j][k] += now;
g[i][j][k] %= p;
}
}
}
}
while (q--) {
ll a, b, c;
cin >> a >> b >> c;
cout << g[a + cnta + 1][b + cntb + 1][c + cntc + 1] << endl;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 13932kb
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: 0ms
memory: 18052kb
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: 0ms
memory: 7856kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 0ms
memory: 24384kb
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: -100
Wrong Answer
time: 0ms
memory: 24416kb
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:
0 0 11 16 11 16 0 0 0 0
result:
wrong answer 1st lines differ - expected: '16', found: '0'