QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#838693#9912. 比赛wosile10 19ms6624kbC++141.1kb2024-12-31 18:24:542024-12-31 18:24:55

Judging History

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

  • [2024-12-31 18:24:55]
  • 评测
  • 测评结果:10
  • 用时:19ms
  • 内存:6624kb
  • [2024-12-31 18:24:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 3005
typedef long long ll;
ll f[N][N],ans[N*2];
int n;
char s[N];
#define mod 998244353
int main(){
    // freopen("d3t1.in","r",stdin);
    // freopen("d3t1.out","wb",stdout);
    scanf("%d",&n);
    scanf("%s",s+1);
    f[0][0]=1;
    int cntr=(s[1]=='R');
    int cntb=(s[1]=='B');
    for(int i=2;i<=n;i++){
        if(s[i]=='R'){
            for(int p=0;p+p<i;p++)for(int q=(i-1>>1);q>=0;q--)if(f[p][q]){
                ll v=f[p][q];
                f[p][q+1]+=v*(cntb-q);
                if(p)f[p-1][q]+=v*p;
                f[p][q]=f[p][q]*(cntr+q-p)%mod;
            }
            ++cntr;
        }
        if(s[i]=='B'){
            for(int p=(i-1>>1);p>=0;p--)for(int q=0;q+q<i;q++)if(f[p][q]){
                ll v=f[p][q];
                f[p+1][q]+=v*(cntr-p);
                if(q)f[p][q-1]+=v*q;
                f[p][q]=f[p][q]*(cntb+p-q)%mod;
            }
            ++cntb;
        }
    }
    for(int p=0;p+p<=n;p++)for(int q=0;q+q<=n;q++)ans[-p-p+q+n]+=f[p][q]%mod;
    for(int i=0;i<=n+n;i++)printf("%d ",ans[i]%mod);
    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: 5992kb

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: 0ms
memory: 3788kb

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: 0ms
memory: 3964kb

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: 0ms
memory: 3832kb

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: 3776kb

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: 3824kb

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: 0
Wrong Answer

Test #7:

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

input:

30
BRBRRBRBBRBRBBRBBRBBRBBRBBRRBR

output:

0 0 0 0 0 0 0 0 0 472322155 341149300 936998100 729294726 -335718952 18043211 -71464279 348424229 33359530 480285544 -5232116 -736825169 195526599 -573377354 299781594 188759114 541199303 672333553 -246996738 539603556 341724777 288097571 204185976 173864534 58699849 413761869 995017144 498609486 30...

result:

wrong answer 13th numbers differ - expected: '663102283', found: '729294726'

Subtask #3:

score: 0
Wrong Answer

Test #13:

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

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 738082219 273075167 933956916 483710858 -529862216 349478558 323236944 845887370 822415713 -745251969 -787646247 517066855 579550040 603938678 -103562364 70589177 738493827 -281811691 508299870 -6809344 -963318512 7985...

result:

wrong answer 26th numbers differ - expected: '313155366', found: '738082219'

Subtask #4:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 2ms
memory: 4140kb

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 143159773 -130826336 714809479 -533220607 465800350 -156726462 -346941541 591273913 451181443 649636991 -157152553 -650726474 -612448003 705232333 340967673 -113548901 -706367203 223756863 -137515183 35149586 891969015 -627983683 71...

result:

wrong answer 31st numbers differ - expected: '908685790', found: '143159773'

Subtask #5:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 19ms
memory: 6624kb

input:

500
RRBBBBRBBBRRRRBRRBBBRBBRRBRBRRBBBBRBRBBBRBBBRBBBBBBRBBRBBBBRRBBBBBBRBBBBBBRBBBBRBRRRRRRBRBBRBBBRBBRRRBRBBRRBBRBBRBBRBRRBBBBBRRRBBBRRBRBRBRRBRBBBRBBBRRRBBRBRBRRRRBBBBBBBRBRRRRRBBBBBBBRBBBRBBRRRBBRRBRRRRRBBBRBRRRRBBBBRBBBRBBBRBBBBRRBRRBRRRBBBBRRBBRRBBBBRRRRBBBBBBBBBRBRRBBRBRBBRRRBBBRBRRRBBBRRBBRBB...

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 -918903508 -156681979 -622370027 -963260171 -94478967 199049823 -870946669 452391224 597960161 790316668 -124589114 725178369 -401870254 800113429 -597045350 ...

result:

wrong answer 72nd numbers differ - expected: '557061980', found: '-918903508'

Subtask #6:

score: 0
Time Limit Exceeded

Test #31:

score: 0
Time Limit Exceeded

input:

3000
RRBBRRBRBBRRRRRBBRBRBRBBBBBRBBRRBBBBBRRBBBRBBBRRRBBRBBBBRRBBRRRRRRRBRRBBRRRRBBRBRRRRRBRRBRRRBRRRRRBBBRBBBRRBBBRRRBRBBBBBRBRBRBRBRBRBBRBRRRRRBBBBBRBBBRRRBBRRRBBRBBRBRBBRRBBRBBBRRBBRRBRBBRRBBBRRBRBRBRRRRRRBBBBRRRBBBRRRBBRRBRBRRBBRRBRRBBBRRRBBRBBBRBRRRRRRBRBBRRBRRBRBRBBBBRRRBBBRBBRBBBBRRRBRRBBBRRB...

output:


result: