QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#834450 | #9912. 比赛 | hhoppitree# | 0 | 0ms | 0kb | C++23 | 2.3kb | 2024-12-27 17:21:10 | 2024-12-27 17:21:11 |
answer
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int N = 505, P = 998244353;
int cnt[N];
long long F[2][N][N >> 1][N >> 1], res[N << 1];
signed main() {
int n = 500;// scanf("%d", &n);
string S; //cin >> S, S = ' ' + S;
for (int i = 1; i <= n; ++i) S += "RB"[i % 2];
// string S; cin >> S, S = ' ' + S;
for (int i = 1; i <= n; ++i) cnt[i] = cnt[i - 1] + (S[i] == 'R');
for (int i = 1; i <= n; ++i) cnt[i] = cnt[i] * 2 - i;
F[0][(S[1] == 'R' && S[2] == 'R') * 2][S[1] == 'B' && S[2] == 'R'][S[1] == 'R' && S[2] == 'B'] = 1;
for (register int i = 2; i < n; ++i) {
for (register int a = 0; a <= i; ++a) {
int b = a - cnt[i];
if (b < 0 || b > i || a + b < 0 || a + b > i) continue;
for (register int c = 0; c * 2 <= i - a - b; ++c) {
int d = ((i - a - b) >> 1) - c;
for (register int e = 0; e * 2 <= i - a - b; ++e) {
int f = ((i - a - b) >> 1) - e, v = F[i & 1][a][c][e] % P;
if (!v) continue;
if (S[i + 1] == 'R') {
F[(i & 1) ^ 1][a + 1][c][e] += 1ll * v * (a + c + f);
F[(i & 1) ^ 1][a][c + 1][e] += 1ll * v * b;
F[(i & 1) ^ 1][a + 1][c + 1][e] += 1ll * v * d;
if (e) F[(i & 1) ^ 1][a + 1][c][e - 1] += 1ll * v * e;
} else {
F[(i & 1) ^ 1][a][c][e] += 1ll * v * (b + d + e);
if (a) F[(i & 1) ^ 1][a - 1][c][e + 1] += 1ll * v * a;
if (c) F[(i & 1) ^ 1][a][c - 1][e] += 1ll * v * c;
F[(i & 1) ^ 1][a][c][e + 1] += 1ll * v * f;
}
F[i & 1][a][c][e] = 0;
}
}
}
}
for (int a = 0; a <= n; ++a) {
int b = a - cnt[n];
for (int c = 0; c <= n / 2; ++c) {
int d = (n - a - b) / 2 - c;
for (int e = 0; e <= n / 2; ++e) {
int f = (n - a - b) / 2 - e;
res[c - d - e + N] += F[n & 1][a][c][e];
}
}
}
for (int i = -n; i <= n; ++i) {
printf("%lld%c", res[i + N] % P, " \n"[i == n]);
}
return 0;
}
详细
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
17 RRBRBRRRBBRRBBBBB
output:
result:
Subtask #2:
score: 0
Time Limit Exceeded
Test #7:
score: 0
Time Limit Exceeded
input:
30 BRBRRBRBBRBRBBRBBRBBRBBRBBRRBR
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #13:
score: 0
Time Limit Exceeded
input:
50 BBBRRRBRRRBBRBRRRBRRRBRRRRRRRBBRRRBBBRRBRRRBBRRRBR
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #19:
score: 0
Time Limit Exceeded
input:
200 RBRBRBBRBRBRRBBRBBRBRBBBRBRRBRBRBRRBRRRBRRBRRRRRBRBBRRBBRBBRBBBBRBRBRBBBRRBBRBRRRBRBRBBBBRBRRRBBBBRRRBRBBRBBBRRRRRBRRRRRBRRRRRRRBBRRBRBBRBBRRRBRRRBRRRRBRBRBRRBBRBBRRBRRRRBBRRBRBRBRRRRBBRBRRBBRRBRBBBBR
output:
result:
Subtask #5:
score: 0
Time Limit Exceeded
Test #25:
score: 0
Time Limit Exceeded
input:
500 RRBBBBRBBBRRRRBRRBBBRBBRRBRBRRBBBBRBRBBBRBBBRBBBBBBRBBRBBBBRRBBBBBBRBBBBBBRBBBBRBRRRRRRBRBBRBBBRBBRRRBRBBRRBBRBBRBBRBRRBBBBBRRRBBBRRBRBRBRRBRBBBRBBBRRRBBRBRBRRRRBBBBBBBRBRRRRRBBBBBBBRBBBRBBRRRBBRRBRRRRRBBBRBRRRRBBBBRBBBRBBBRBBBBRRBRRBRRRBBBBRRBBRRBBBBRRRRBBBBBBBBBRBRRBBRBRBBRRRBBBRBRRRBBBRRBBRBB...
output:
result:
Subtask #6:
score: 0
Time Limit Exceeded
Test #31:
score: 0
Time Limit Exceeded
input:
3000 RRBBRRBRBBRRRRRBBRBRBRBBBBBRBBRRBBBBBRRBBBRBBBRRRBBRBBBBRRBBRRRRRRRBRRBBRRRRBBRBRRRRRBRRBRRRBRRRRRBBBRBBBRRBBBRRRBRBBBBBRBRBRBRBRBRBBRBRRRRRBBBBBRBBBRRRBBRRRBBRBBRBRBBRRBBRBBBRRBBRRBRBBRRBBBRRBRBRBRRRRRRBBBBRRRBBBRRRBBRRBRBRRBBRRBRRBBBRRRBBRBBBRBRRRRRRBRBBRRBRRBRBRBBBBRRRBBBRBBRBBBBRRRBRRBBBRRB...