QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #766512 | #9536. Athlete Welcome Ceremony | ospoasa | WA | 7ms | 50140kb | C++23 | 2.8kb | 2024-11-20 17:33:49 | 2024-11-20 17:33:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 305;
const LL mod = 998244353;
LL dp[2][N][N][3], f[N][N][N], A[N][N][N]; // 前i个字符, 选j个a, k个b
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
string S;
cin >> S;
S = ' ' + S;
if(S[1] == 'a') dp[1][1][0][0] = 1;
else if(S[1] == 'b') dp[1][0][1][1] = 1;
else if(S[1] == 'c') dp[1][0][0][2] = 1;
else dp[1][1][0][0] = dp[1][0][1][1] = dp[1][0][0][2] = 1;
int up = 0, now = 1;
for(int i = 2; i <= n; i++)
{
up = (i + 1) % 2;
now = up ^ 1;
for(int j = 0; j <= i; j++)
{
for(int k = 0; k <= i; k++)
{
if(j + k > i) break;
if(S[i] == 'a' || S[i] == '?') {
if(j > 0)
dp[now][j][k][0] = dp[up][j - 1][k][1] + dp[up][j - 1][k][2];
dp[now][j][k][0] %= mod;
}
if(S[i] == 'b' || S[i] == '?') {
if(k > 0)
dp[now][j][k][1] = dp[up][j][k - 1][0] + dp[up][j][k - 1][2];
dp[now][j][k][1] %= mod;
}
if(S[i] == 'c' || S[i] == '?') {
if(j + k < i)
dp[now][j][k][2] = dp[up][j][k][0] + dp[up][j][k][1];
dp[now][j][k][2] %= mod;
}
}
}
for(int j = 0; j <= i; j++) {
for(int k = 0; k <= i; k++) {
dp[up][j][k][0] = dp[up][j][k][1] = dp[up][j][k][2] = 0;
}
}
}
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= n; j++) {
if(i + j > n) break;
for(int h = 0; h < 3; h++) {
A[i + 1][j + 1][n - i - j + 1] += dp[now][i][j][h];
A[i + 1][j + 1][n - i - j + 1] %= mod;
}
}
}
for(int i = 1; i <= n + 1; i++)
for(int j = 1; j <= n + 1; j++)
for(int k = 1; k <= n + 1; k++) {
f[i][j][k] = f[i - 1][j][k] + f[i][j - 1][k] + f[i][j][k - 1]
- f[i - 1][j - 1][k] - f[i - 1][j][k - 1] - f[i][j - 1][k - 1]
+ f[i - 1][j - 1][k - 1] + A[i][j][k] + mod * 3;
f[i][j][k] %= mod;
}
int ca = 0, cb = 0, cc = 0;
for(int i = 1; i <= n; i++) {
if(S[i] == 'a') ca++;
else if(S[i] == 'b') cb++;
else if(S[i] == 'c') cc++;
}
int x2, y2, z2;
for(int i = 1; i <= q; i++) {
cin >> x2 >> y2 >> z2;
x2 = min(n, x2 + ca);
y2 = min(n, y2 + cb);
z2 = min(n, z2 + cc);
x2++, y2++, z2++;
// cout << x2 << ' ' << y2 << ' ' << z2 << '\n';
cout << f[x2][y2][z2] << '\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5980kb
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: 1ms
memory: 5976kb
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: 5540kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 2ms
memory: 8144kb
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: 0
Accepted
time: 1ms
memory: 8144kb
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:
16 16 11 16 11 16 16 5 11 0
result:
ok 10 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 15580kb
input:
50 100 ?abacbacab?cbcbcb?acabcbabcbcacbababc?caba?acacbca 8 3 8 2 4 8 8 7 3 0 9 2 10 8 7 7 6 5 4 10 2 6 9 3 3 6 6 9 10 8 2 5 8 8 1 0 3 5 0 1 0 6 5 0 8 6 5 5 1 7 9 7 7 10 4 7 5 6 6 4 10 1 2 4 1 7 10 0 8 7 6 3 1 9 1 4 7 2 8 4 0 8 6 1 5 10 4 5 8 2 5 8 4 4 5 9 5 2 1 1 10 9 4 10 1 8 4 3 8 9 9 8 0 1 0 8 0...
output:
8 8 8 0 8 8 6 8 8 8 8 0 0 0 1 8 4 8 8 8 2 4 1 8 1 6 0 2 8 6 8 8 1 4 2 8 8 0 0 8 2 0 8 8 8 4 8 8 8 8 2 0 0 4 8 8 1 8 7 6 7 0 8 8 8 0 4 7 8 4 0 8 0 4 8 8 8 7 8 4 7 2 8 8 8 0 2 2 8 8 8 4 4 0 8 0 8 8 1 1
result:
ok 100 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 17232kb
input:
50 100 b????????bca?????c?b??ca?acac?b?b???ca?ab???a?a??? 35 43 36 12 49 47 7 11 34 38 44 22 42 17 10 49 8 38 18 26 44 6 18 14 28 29 6 48 32 47 29 15 48 1 5 33 24 17 18 10 27 32 19 10 34 2 23 9 14 24 39 46 12 34 9 49 26 21 8 46 43 43 3 31 16 2 8 27 7 24 41 35 17 25 31 0 13 47 24 31 23 33 40 30 36 39...
output:
34272000 31599360 497244 34272000 17637520 12290752 34272000 93044 415832 34272000 34272000 0 34272000 16360704 27933952 0 34272000 33886976 7896832 12290752 718 24 0 34272000 34272000 0 34272000 34272000 34272000 32254720 0 5666944 34256640 34272000 34272000 12290752 30493248 34256640 20630016 0 10...
result:
ok 100 lines
Test #8:
score: 0
Accepted
time: 7ms
memory: 48676kb
input:
100 1000 c?cbababcabacbacbacacbacabcbabababacababcbcab?cbabacbacbcbcacbab?bcabcbcababcacbabacbcb?babcbab?baca 13 11 4 4 17 20 14 5 2 16 14 15 8 12 17 19 5 11 5 17 12 20 7 6 19 10 1 6 5 0 13 1 9 7 17 1 20 4 16 11 12 18 19 2 16 18 1 11 19 16 3 7 1 0 6 9 16 6 9 16 6 20 7 0 16 20 1 2 8 16 5 20 18 14 18 ...
output:
16 15 14 16 16 16 16 16 8 2 16 8 16 16 16 16 16 2 16 16 16 0 1 16 16 5 1 5 16 16 16 16 16 15 16 13 16 15 2 16 16 1 8 16 16 16 15 0 16 15 16 16 16 16 8 8 16 16 16 16 16 16 8 16 16 1 8 8 16 16 1 16 1 0 16 2 2 16 7 16 16 8 16 16 16 16 1 16 14 16 16 16 16 5 16 16 14 16 11 16 15 11 2 1 8 16 16 7 16 5 16 ...
result:
ok 1000 lines
Test #9:
score: -100
Wrong Answer
time: 4ms
memory: 50140kb
input:
100 1000 ?????c??????????????????????????b???a????a?????????????????????????c???????????????????????????????? 43 38 20 27 40 32 39 27 33 28 50 43 50 3 46 38 46 14 42 48 10 45 25 28 49 10 49 38 17 42 41 49 22 41 18 44 46 47 25 17 44 35 34 43 22 47 42 32 32 44 40 36 41 24 45 38 45 49 44 18 42 34 32 43...
output:
804458366 986514507 631676168 668774326 10104 806873682 457652893 556612659 833031739 194151457 769278037 274041326 594216165 183174115 939173449 604062764 737118944 281846238 379026979 660541372 959207727 575057371 385668393 989871351 166230586 907706324 523034330 586950612 67939963 816607907 42635...
result:
wrong answer 1st lines differ - expected: '490475656', found: '804458366'