QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#834424#9912. 比赛hhoppitree#0 82ms15304kbC++142.2kb2024-12-27 17:00:022024-12-27 17:00:04

Judging History

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

  • [2024-12-27 17:00:04]
  • 评测
  • 测评结果:0
  • 用时:82ms
  • 内存:15304kb
  • [2024-12-27 17:00:02]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

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 >> 1][N >> 1], 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) {
        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 * 2 <= i - a - b; ++c) {
                int d = ((i - a - b) >> 1) - c;
                for (int e = 0; e * 2 <= i - a - b; ++e) {
                    int f = ((i - a - b) >> 1) - 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 + c + f));
                        add(F[(i & 1) ^ 1][a][c + 1][e], 1ll * v * b);
                        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);
                    } else {
                        add(F[(i & 1) ^ 1][a][c][e], 1ll * v * (b + d + e));
                        if (a) add(F[(i & 1) ^ 1][a - 1][c][e + 1], 1ll * v * a);
                        if (c) add(F[(i & 1) ^ 1][a][c - 1][e], 1ll * v * c);
                    }
                    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; ++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
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3872kb

input:

17
RRBRBRRRBBRRBBBBB

output:

0 15759360 186485760 778692607 358655477 268868821 308239967 485969316 508959962 433792678 189835653 841376776 539329593 659356789 979822033 356335653 528854960 89259246 215533821 306213120 3168000 0 0 0 0 0 0 0 0 0 0 0 0 0 0

result:

wrong answer 2nd numbers differ - expected: '24883200', found: '15759360'

Subtask #2:

score: 0
Wrong Answer

Test #7:

score: 0
Wrong Answer
time: 1ms
memory: 4340kb

input:

30
BRBRRBRBBRBRBBRBBRBBRBBRBBRRBR

output:

0 0 0 0 0 0 0 0 0 985969221 828116664 421935966 630329617 351016060 324662189 61725288 604442383 671482680 727108528 103617670 299709653 721878228 90166267 23951927 258494192 636950576 506477664 239884656 284585884 112286984 692413292 52123631 729018143 209821334 137125468 338623033 673286052 627844...

result:

wrong answer 10th numbers differ - expected: '472322155', found: '985969221'

Subtask #3:

score: 0
Wrong Answer

Test #13:

score: 0
Wrong Answer
time: 0ms
memory: 4932kb

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 969017813 187954472 923757621 561822111 945075864 636678810 393094427 174807693 770606677 22357523 153763096 862658247 890749027 980542132 991840990 837746390 104786358 422417580 393754252 7202490 589712458 828014176 796589387 745900575 588566841 5...

result:

wrong answer 23rd numbers differ - expected: '723021899', found: '969017813'

Subtask #4:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 82ms
memory: 15304kb

input:

200
RBRBRBBRBRBRRBBRBBRBRBBBRBRRBRBRBRRBRRRBRRBRRRRRBRBBRRBBRBBRBBBBRBRBRBBBRRBBRBRRRBRBRBBBBRBRRRBBBBRRRBRBBRBBBRRRRRBRRRRRBRRRRRRRBBRRBRBBRBBRRRBRRRBRRRRBRBRBRRBBRBBRRBRRRRBBRRBRBRBRRRRBBRBRRBBRRBRBBBBR

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 749304236 972049420 29541247 78467596 686023398 942074155 852913511 450253124 759923327 170224809 3509571 469156456 703353964 460677216 890614849 507607936 56041716 742629448 590067902 169008028 528192000 484610795 766679036 115963154 7241050...

result:

wrong answer 30th numbers differ - expected: '745609274', found: '749304236'

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

output:


result: