QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#834450#9912. 比赛hhoppitree#0 0ms0kbC++232.3kb2024-12-27 17:21:102024-12-27 17:21:11

Judging History

你现在查看的是最新测评结果

  • [2024-12-27 17:21:11]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-12-27 17:21:10]
  • 提交

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...

output:


result: