QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#838693 | #9912. 比赛 | wosile | 10 | 19ms | 6624kb | C++14 | 1.1kb | 2024-12-31 18:24:54 | 2024-12-31 18:24:55 |
Judging History
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...