QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#834416 | #9912. 比赛 | hhoppitree# | 0 | 0ms | 0kb | C++14 | 2.5kb | 2024-12-27 16:54:32 | 2024-12-27 16:54:32 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 505, P = 998244353;
void add(int &x, long long y) {
y += x;
x = y - (((__int128)y * 18479187002) >> 64) * P;
}
int cnt[N], F[2][N][N][N], res[N << 1];
signed main() {
int n; scanf("%d", &n);
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 (int i = 2; i < n; ++i) {
memset(F[(i & 1) ^ 1], 0, sizeof(F[(i & 1) ^ 1]));
for (int a = 0; a <= i; ++a) {
int b = a - cnt[i];
if (b < 0 || b > i || a + b < 0 || a + b > i) continue;
for (int c = 0; c <= (i - a - b) / 2; ++c) {
int d = (i - a - b) / 2 - c;
for (int e = 0; e <= (i - a - b) / 2; ++e) {
int f = (i - a - b) / 2 - e, v = F[i & 1][a][c][e];
if (!v) continue;
if (S[i + 1] == 'R') {
add(F[(i & 1) ^ 1][a + 1][c][e], 1ll * v * a);
add(F[(i & 1) ^ 1][a][c + 1][e], 1ll * v * b);
add(F[(i & 1) ^ 1][a + 1][c][e], 1ll * v * c);
add(F[(i & 1) ^ 1][a + 1][c + 1][e], 1ll * v * d);
if (e) add(F[(i & 1) ^ 1][a + 1][c][e - 1], 1ll * v * e);
add(F[(i & 1) ^ 1][a + 1][c][e], 1ll * v * f);
} else {
if (a) add(F[(i & 1) ^ 1][a - 1][c][e + 1], 1ll * v * a);
add(F[(i & 1) ^ 1][a][c][e], 1ll * v * b);
if (c) add(F[(i & 1) ^ 1][a][c - 1][e], 1ll * v * c);
add(F[(i & 1) ^ 1][a][c][e], 1ll * v * d);
add(F[(i & 1) ^ 1][a][c][e], 1ll * v * e);
add(F[(i & 1) ^ 1][a][c][e + 1], 1ll * v * f);
}
}
}
}
}
for (int a = 0; a <= n; ++a) {
int b = a - cnt[n];
for (int c = 0; c <= n; ++c) {
int d = (n - a - b) / 2 - c;
for (int e = 0; e <= n; ++e) {
int f = (n - a - b) / 2 - e;
add(res[c - d - e + N], F[n & 1][a][c][e]);
}
}
}
for (int i = -n; i <= n; ++i) {
printf("%d%c", res[i + N], " \n"[i == n]);
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Memory Limit Exceeded
Test #1:
score: 0
Memory Limit Exceeded
input:
17 RRBRBRRRBBRRBBBBB
output:
0 24883200 242611200 501356541 849327599 494325665 823181277 903086281 266727081 332891457 910769886 319278309 251084707 537868029 253839295 412441055 638651452 562229207 730747129 511349760 4043520 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
Subtask #2:
score: 0
Memory Limit Exceeded
Test #7:
score: 0
Memory Limit Exceeded
input:
30 BRBRRBRBBRBRBBRBBRBBRBBRBBRRBR
output:
0 0 0 0 0 0 0 0 0 472322155 341149300 936998100 663102283 980872253 804068473 305737372 759992827 435714306 53578403 194953860 138874148 917648147 411689713 842676190 596563600 507144388 897742572 313213524 497244336 51840810 817612587 54680186 71915231 72873026 821631943 995017144 498609486 3059714...
result:
Subtask #3:
score: 0
Memory Limit Exceeded
Test #13:
score: 0
Memory Limit Exceeded
input:
50 BBBRRRBRRRBBRBRRRBRRRBRRRRRRRBBRRRBBBRRBRRRBBRRRBR
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 840671540 723021899 421289556 784273730 313155366 411853797 393531340 678567 633540304 934617986 894818850 619909812 260582295 277020059 767648419 229952267 653528115 836441240 93744680 503596241 14610311 176768975 411266579 97000158 68055577 77093992 819156...
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
Runtime Error
Test #31:
score: 0
Runtime Error
input:
3000 RRBBRRBRBBRRRRRBBRBRBRBBBBBRBBRRBBBBBRRBBBRBBBRRRBBRBBBBRRBBRRRRRRRBRRBBRRRRBBRBRRRRRBRRBRRRBRRRRRBBBRBBBRRBBBRRRBRBBBBBRBRBRBRBRBRBBRBRRRRRBBBBBRBBBRRRBBRRRBBRBBRBRBBRRBBRBBBRRBBRRBRBBRRBBBRRBRBRBRRRRRRBBBBRRRBBBRRRBBRRBRBRRBBRRBRRBBBRRRBBRBBBRBRRRRRRBRBBRRBRRBRBRBBBBRRRBBBRBBRBBBBRRRBRRBBBRRB...