QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#834434	#9912. 比赛	hhoppitree^#	0	163ms	19452kb	C++14	4.5kb	2024-12-27 17:10:36	2024-12-27 17:10:38

Judging History

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

[2024-12-27 17:10:38]
评测

测评结果：0
用时：163ms
内存：19452kb

查看

[2024-12-27 17:10:36]
提交

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], mn[2][N][N], mx[2][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;
    mn[0][(S[1] == 'R' && S[2] == 'R') * 2][S[1] == 'B' && S[2] == 'R'] = mx[0][(S[1] == 'R' && S[2] == 'R') * 2][S[1] == 'B' && S[2] == 'R'] = (S[1] == 'R' && S[2] == 'B');
    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 = mn[i & 1][a][c]; e <= mx[i & 1][a][c]; ++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);
                        if (a || c || f) {
                            mn[(i & 1) ^ 1][a + 1][c] = min(mn[(i & 1) ^ 1][a + 1][c], e);
                            mx[(i & 1) ^ 1][a + 1][c] = max(mx[(i & 1) ^ 1][a + 1][c], e);
                        }
                        if (b) {
                            mn[(i & 1) ^ 1][a][c + 1] = min(mn[(i & 1) ^ 1][a][c + 1], e);
                            mx[(i & 1) ^ 1][a][c + 1] = max(mx[(i & 1) ^ 1][a][c + 1], e);
                        }
                        if (d) {
                            mn[(i & 1) ^ 1][a + 1][c + 1] = min(mn[(i & 1) ^ 1][a + 1][c + 1], e);
                            mx[(i & 1) ^ 1][a + 1][c + 1] = max(mx[(i & 1) ^ 1][a + 1][c + 1], e);
                        }
                        if (e) {
                            mn[(i & 1) ^ 1][a + 1][c] = min(mn[(i & 1) ^ 1][a + 1][c], e - 1);
                            mx[(i & 1) ^ 1][a + 1][c] = max(mx[(i & 1) ^ 1][a + 1][c], e - 1);
                        }
                    } 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);
                        add(F[(i & 1) ^ 1][a][c][e + 1], 1ll * v * f);
                        if (b || d || e) {
                            mn[(i & 1) ^ 1][a][c] = min(mn[(i & 1) ^ 1][a][c], e);
                            mx[(i & 1) ^ 1][a][c] = max(mx[(i & 1) ^ 1][a][c], e);
                        }
                        if (a) {
                            mn[(i & 1) ^ 1][a - 1][c] = min(mn[(i & 1) ^ 1][a - 1][c], e + 1);
                            mx[(i & 1) ^ 1][a - 1][c] = max(mx[(i & 1) ^ 1][a - 1][c], e + 1);
                        }
                        if (c) {
                            mn[(i & 1) ^ 1][a][c - 1] = min(mn[(i & 1) ^ 1][a][c - 1], e);
                            mx[(i & 1) ^ 1][a][c - 1] = max(mx[(i & 1) ^ 1][a][c - 1], e);
                        }
                        if (f) {
                            mn[(i & 1) ^ 1][a][c] = min(mn[(i & 1) ^ 1][a][c], e + 1);
                            mx[(i & 1) ^ 1][a][c] = max(mx[(i & 1) ^ 1][a][c], e + 1);
                        }
                    }
                    F[i & 1][a][c][e] = 0;
                }
                mn[i & 1][a][b] = 1e9, mx[i & 1][a][b] = -1e9;
            }
        }
    }
    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;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 1ms

memory: 8260kb

input:

17
RRBRBRRRBBRRBBBBB

output:

0 24883200 242611200 453649406 514369013 695353361 842262851 921022049 354587489 663997443 367074190 719137041 414614734 244930458 60884310 512498168 219951746 776027311 120613056 9792 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

result:

wrong answer 4th numbers differ - expected: '501356541', found: '453649406'

Subtask #2:

score: 0

Wrong Answer

Test #7:

score: 0

Wrong Answer

time: 0ms

memory: 8100kb

input:

30
BRBRRBRBBRBRBBRBBRBBRBBRBBRRBR

output:

0 0 0 0 0 0 0 0 0 1194509 662113098 117964252 411799897 203573717 761415000 497574911 596038736 984174584 219913249 421656525 578431696 149506129 386775651 662073224 961832179 536907315 282045134 162196452 861602242 207084443 422445039 587619071 744506024 586927593 235847216 349582125 704319298 9562...

result:

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

Subtask #3:

score: 0

Wrong Answer

Test #13:

score: 0

Wrong Answer

time: 2ms

memory: 8772kb

input:

50
BBBRRRBRRRBBRBRRRBRRRBRRRRRRRBBRRRBBBRRBRRRBBRRRBR

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1244160 609127827 677021687 816944618 57970068 4179754 897673092 862143109 120038536 495690483 378200261 89118994 442271945 175115586 88388218 150990002 238900847 128972318 775183191 132044484 172937173 730347632 733929895 345974650 869449108 304908473 4693485...

result:

wrong answer 21st numbers differ - expected: '0', found: '1244160'

Subtask #4:

score: 0

Wrong Answer

Test #19:

score: 0

Wrong Answer

time: 163ms

memory: 19452kb

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 110835648 968567949 440381439 458983722 60745218 614948017 26567880 238545802 329098844 9664219 646167357 319409571 10182368 335899301 974334798 280466345 70016675 13625636 631033922 209663894 111346101 575667622 445171803 287463451 239896641...

result:

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

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