QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#834451#9912. 比赛hhoppitree#40 66ms52792kbC++232.2kb2024-12-27 17:21:362024-12-27 17:21:37

Judging History

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

  • [2024-12-27 17:21:37]
  • 评测
  • 测评结果:40
  • 用时:66ms
  • 内存:52792kb
  • [2024-12-27 17:21:36]
  • 提交

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; 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 (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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 5988kb

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:

ok 35 numbers

Test #2:

score: 10
Accepted
time: 1ms
memory: 6208kb

input:

14
RBRBBBRBRBRBRB

output:

0 0 0 162 10062 360546 3876582 28262586 118720710 362734314 769743006 207566581 409796473 179843989 746858754 304375278 89275314 10653918 209466 0 0 0 0 0 0 0 0 0 0

result:

ok 29 numbers

Test #3:

score: 10
Accepted
time: 1ms
memory: 8076kb

input:

16
RBRBBRBBRRRRBRRR

output:

0 0 0 0 0 0 0 0 0 7464960 189112320 805787647 102289397 607018967 263100304 760262444 725591771 330725079 212483889 738101147 418922469 740663294 62208000 0 0 0 0 0 0 0 0 0 0

result:

ok 33 numbers

Test #4:

score: 10
Accepted
time: 1ms
memory: 6160kb

input:

15
BBBRBBBBBBBRBBB

output:

0 0 0 0 0 0 0 0 0 0 0 569397247 734051576 543732211 551111645 463249905 893070070 569397247 0 0 0 0 0 0 0 0 0 0 0 0 0

result:

ok 31 numbers

Test #5:

score: 10
Accepted
time: 0ms
memory: 7852kb

input:

16
BBBBBBBBBRRBBBBB

output:

0 0 0 0 0 0 0 0 0 0 0 0 595832823 580263879 355704698 695840452 92223157 421936853 227196767 0 0 0 0 0 0 0 0 0 0 0 0 0 0

result:

ok 33 numbers

Test #6:

score: 10
Accepted
time: 0ms
memory: 7968kb

input:

15
BBBBBBBBBBRBBBB

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 756797435 193421293 193421293 185636821 0 0 0 0 0 0 0 0 0 0 0 0 0 0

result:

ok 31 numbers

Subtask #2:

score: 10
Accepted

Test #7:

score: 10
Accepted
time: 1ms
memory: 8208kb

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:

ok 61 numbers

Test #8:

score: 10
Accepted
time: 2ms
memory: 12076kb

input:

22
BBRBBBBBBRRBBBBBRBBRRR

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 924987037 156012064 107229157 248572175 432214610 406077427 757195611 771797280 158444708 188622978 686829181 401546354 42086613 449742960 705260458 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

result:

ok 45 numbers

Test #9:

score: 10
Accepted
time: 1ms
memory: 8096kb

input:

20
BBRRBRBRRBRBRBBBRBBR

output:

0 0 0 0 0 286654464 222724085 735477518 879768762 657155621 374608160 460760901 656626201 53371769 887650550 244126084 566589532 369043471 13985447 545833072 665867348 402681618 982192403 980096579 75631823 459258583 316493810 14432256 0 0 0 0 0 0 0 0 0 0 0 0 0

result:

ok 41 numbers

Test #10:

score: 10
Accepted
time: 0ms
memory: 22312kb

input:

30
BBBBBBBBBBBBRRRRRRRRRRRRRRRRRR

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 0 0 72334032 773765874 668869580 537072304 212520714 45699554 506161101 586251470 769359418 430456696 225960959 730416214 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

result:

ok 61 numbers

Test #11:

score: 10
Accepted
time: 1ms
memory: 8164kb

input:

30
BBBBBBBBBBBBBBBBBBRRBBBBBBBBBR

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 932292693 684973968 256288178 934546083 837322348 421266285 493934008 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

result:

ok 61 numbers

Test #12:

score: 10
Accepted
time: 0ms
memory: 7912kb

input:

30
BBBBBBBBBBBBBBRRBBBBBBBBBBBBBR

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 134057753 834266559 817644314 588299868 727219703 470864360 988271006 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

result:

ok 61 numbers

Subtask #3:

score: 10
Accepted

Test #13:

score: 10
Accepted
time: 0ms
memory: 26912kb

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:

ok 101 numbers

Test #14:

score: 10
Accepted
time: 0ms
memory: 8188kb

input:

30
BRRBRBRRBBBRRBBBBBRBRRBRBBRBBB

output:

0 0 0 0 0 0 577002683 677691869 405169704 881214934 522606625 485568739 268429513 865028369 394347342 453955082 864056906 944433445 145565620 567872744 393691753 186892897 922995475 732239080 38136676 808302887 475120602 534045005 594213186 396919948 513486569 540062329 366918440 444240351 247203479...

result:

ok 61 numbers

Test #15:

score: 10
Accepted
time: 0ms
memory: 11196kb

input:

46
BBBBRBBRBBBRRRRRBRBRBRRBRRRBRBBBBRBRBRRBBRRBRR

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 660761508 644702590 897844805 750106369 686938853 932481915 574174221 294213960 668854749 706431613 100498282 960168080 353092076 343099522 183983669 107126533 718310464 498363183 369572616 972830870 716934606 763584223 595161946 338630761 717786690 849278305 262900429 ...

result:

ok 93 numbers

Test #16:

score: 10
Accepted
time: 3ms
memory: 18276kb

input:

50
BBBBBBBBBBBBBBBBRRRRRRRRRRRRRRRRBBBBBBBBBBBBBBBBBB

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 831392418 604328086 961184705 819434558 450033872 572811813 637284475 638881547 844766974 157789854 461172724 939131107 246938607 141044738 596024030 462151101 314563907 17327804 409217009 118114813 134339259 787410036 777008722 896388601 748783660 851950968 85661...

result:

ok 101 numbers

Test #17:

score: 10
Accepted
time: 1ms
memory: 6292kb

input:

49
RBBBBBRBRBBBBBBBBBBBBBBBBRBBBBBRBBBBRBBBBBBBBBBBR

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 0 0 0 0 0 0 0 0 0 607905029 969689245 927531367 354997122 672606662 890595880 747744666 352270561 749008986 17901987 544305436 246979810 221979365 894641324 406170420 985309021 772832843 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...

result:

ok 99 numbers

Test #18:

score: 10
Accepted
time: 0ms
memory: 5912kb

input:

50
BBBBBBBBBBRBBBBBBBBBBBBBRBBBBBRBRBBBBBBBBBBBBBBBRB

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 0 0 0 0 0 0 0 0 0 0 0 0 662189982 50268982 516797152 800043454 523612648 23838524 677535558 4054488 381467635 589829657 587271506 883407480 54487000 290015930 597531274 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 0 0 0 0 0 0 0 0...

result:

ok 101 numbers

Subtask #4:

score: 10
Accepted

Test #19:

score: 10
Accepted
time: 59ms
memory: 52792kb

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 745609274 908685790 381548860 264974180 959826982 760604252 483130221 835386541 316125466 260589275 814282660 145470527 384293777 365073535 965306655 674115093 763471295 941625609 834987587 385920270 296085371 863016777 168400617 385101278 31...

result:

ok 401 numbers

Test #20:

score: 10
Accepted
time: 8ms
memory: 21972kb

input:

127
BRBBBRRRBBRRBRBBBRRRBBBRRRBBBBBRBBBBBRBBRRBBBRBBRBRBBRRBBRRBRBRBRBBBBBRRRBRBBBRRBBBBRRBRRBRBBRRRBRBBBRRRBBRRRBBRRBRBRBBBRRBRRBB

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 892965774 607306820 653562192 706656579 249289590 168840319 746524666 910950632 820231829 24281672 328887776 681054091 310407940 294888860 527266886 658228102 389793690 762714214 43951323 383435616 55968202 898934801 161585759 971473439 774966775 570051632...

result:

ok 255 numbers

Test #21:

score: 10
Accepted
time: 66ms
memory: 48208kb

input:

189
BBRBBRRBBRRRBBRBRRBRBBBBRRBBBBBRBRBRRBBRBRRRRBRRRBRRBBBRBRRRBBBRRBRRRBRBBBRBRRRRBRBRBRRBBBRRRBRBRBBRBBRBBBBRRBBBRBRBBRRRRBBRBBBRRRRRBBRRRRRRRRBRBRBBRRRBRRBRBRBRRBRBRBRBBBRBRBRRRBRBRRBBBRBBR

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 531665400 25736208 604919590 590386634 974667105 292393819 703257642 868394065 735413210 212769177 223384193 263497431 768513865 137480479 359064465 215776751 418095264 370622263 122824293 545709278 172213253 426810265 431481313 439059761 732850090 9619858...

result:

ok 379 numbers

Test #22:

score: 10
Accepted
time: 19ms
memory: 41572kb

input:

197
RBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBRRRRRRRRRBBBBBBBBBBBBBBBBBBBBBBBBBBBBBRRRRRRRRRRRRRRRRRRRRRRRRRRRRRBBBBBBBBBBBBBBBBRRRRRRRRRRRRRRRRRRRRRRBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23625400 731155554 707954979 756051993 710417147 268240200 527021965 302263442 283629134 387948987 133643929 914803161 789693911 426823172 55389...

result:

ok 395 numbers

Test #23:

score: 10
Accepted
time: 3ms
memory: 8556kb

input:

197
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBRBBBBBBRBBBBBBRBBRRBBBBBRBBBBRRBBBBBRBBBBBBBBRBBBBBBBBBBBBBBBBBRBBBBBBBBBRBBBBBBBBBBRBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBRBBBBBBBBBBBBBBBBBBRRBRBBBBBBBBBBBBBBBBBBBBRBBBBBB

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

result:

ok 395 numbers

Test #24:

score: 10
Accepted
time: 3ms
memory: 8912kb

input:

200
BBBBBBBBBBBRBBBBBBBRBBBBBBBBBBBBBBBBBRBBBBBBBRBBBBRBBBBBBBBBBBBBBBRBBRBBBBBBBBBBBBBBBBRBBBBBBBBBBBBBBBBBBBBBBRBBBBBBBBBBBBRBBBBBBBRRBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBRRBBBRBBBBRBBBBBRBRBB

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

result:

ok 401 numbers

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: