QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#229860 | #7564. Game | c20230507 | AC ✓ | 20061ms | 136848kb | C++14 | 3.4kb | 2023-10-28 17:04:13 | 2023-10-28 17:04:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
int n,f[maxn],inv[maxn],g[maxn],vs[maxn];
string to[maxn],w[maxn];
int qpow(int x,int y){
int val=1;
while(y){
if(y&1)val=val*x%mod;
x=x*x%mod,y/=2;
}
return val;
}
int C(int x,int y){
return f[x]*inv[y]%mod*inv[x-y]%mod;
}
int sum[27][27][27][27][27];
void bk(){
for(int i=0;i<=25;i++){
for(int j=0;j<=25;j++){
for(int k=0;k<=25;k++){
for(int l=0;l<=25;l++){
for(int r=0;r<=25;r++)sum[i][j][k][l][r]=0;
}
}
}
}
}
int l[maxn],r[maxn];
void solve_sum(int s){
for(int i=1;i<26-((s>>0)&1);i++){
for(int j=0;j<26-((s>>1)&1);j++){
for(int k=0;k<26-((s>>2)&1);k++){
for(int l=0;l<26-((s>>3)&1);l++){
for(int r=0;r<26-((s>>4)&1);r++){
sum[i][j][k][l][r]+=sum[i-1][j][k][l][r];
}
}
}
}
}
for(int i=0;i<26-((s>>0)&1);i++){
for(int j=1;j<26-((s>>1)&1);j++){
for(int k=0;k<26-((s>>2)&1);k++){
for(int l=0;l<26-((s>>3)&1);l++){
for(int r=0;r<26-((s>>4)&1);r++){
sum[i][j][k][l][r]+=sum[i][j-1][k][l][r];
}
}
}
}
}
for(int i=0;i<26-((s>>0)&1);i++){
for(int j=0;j<26-((s>>1)&1);j++){
for(int k=1;k<26-((s>>2)&1);k++){
for(int l=0;l<26-((s>>3)&1);l++){
for(int r=0;r<26-((s>>4)&1);r++){
sum[i][j][k][l][r]+=sum[i][j][k-1][l][r];
}
}
}
}
}
for(int i=0;i<26-((s>>0)&1);i++){
for(int j=0;j<26-((s>>1)&1);j++){
for(int k=0;k<26-((s>>2)&1);k++){
for(int l=1;l<26-((s>>3)&1);l++){
for(int r=0;r<26-((s>>4)&1);r++){
sum[i][j][k][l][r]+=sum[i][j][k][l-1][r];
}
}
}
}
}
for(int i=0;i<26-((s>>0)&1);i++){
for(int j=0;j<26-((s>>1)&1);j++){
for(int k=0;k<26-((s>>2)&1);k++){
for(int l=0;l<26-((s>>3)&1);l++){
for(int r=1;r<26-((s>>4)&1);r++){
sum[i][j][k][l][r]+=sum[i][j][k][l][r-1];
}
}
}
}
}
}
void init(){
f[0]=1;
for(int i=1;i<=n;i++)f[i]=f[i-1]*i%mod;
inv[n]=qpow(f[n],mod-2);
for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
for(int s=0;s<32;s++){
bk();
for(int i=1;i<=n;i++){
int flag=0;
for(int j=0;j<5;j++){
int v=to[i][j]-'A';
if(w[i][j]=='=')l[j]=r[j]=v;
else if(w[i][j]=='<')l[j]=0,r[j]=v-1;
else l[j]=v+1,r[j]=25;
if((s>>j)&1)r[j]--;
if(l[j]>r[j])flag=1;
}
if(flag)continue;
for(int pos=0;pos<32;pos++){
int base[5],flag=1;
for(int j=0;j<5;j++){
if((pos>>j)&1)base[j]=r[j]+1,flag=-flag;
else base[j]=l[j];
}
sum[base[0]][base[1]][base[2]][base[3]][base[4]]+=flag;
}
}
solve_sum(s);
int val=1;
for(int j=0;j<5;j++)if((s>>j)&1)val=-val;
for(int i=0;i<26-((s>>0)&1);i++){
for(int j=0;j<26-((s>>1)&1);j++){
for(int k=0;k<26-((s>>2)&1);k++){
for(int l=0;l<26-((s>>3)&1);l++){
for(int r=0;r<26-((s>>4)&1);r++)g[sum[i][j][k][l][r]]+=val;
}
}
}
}
}
}
//sb容斥
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>to[i]>>w[i];
init();
for(int i=0;i<=n;i++)vs[i]=g[i]*f[i]%mod;
for(int i=0;i<=n;i++){
for(int j=i+1;j<=n;j++){
vs[i]=(vs[i]+g[j]*f[j]%mod*inv[j-i]%mod)%mod;
}
}
for(int i=1;i<=n;i++){
int ans=(vs[i-1]*(n-i+1)%mod-vs[i]+mod)%mod;
cout<<(ans+mod)%mod<<" ";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2202ms
memory: 134728kb
input:
2 FAKER >>>>> CHOVY =====
output:
0 2
result:
ok 2 number(s): "0 2"
Test #2:
score: 0
Accepted
time: 2235ms
memory: 136768kb
input:
3 BVHUQ ><>>< YJCEQ <<><< SXXWZ >>==>
output:
1 4 0
result:
ok 3 number(s): "1 4 0"
Test #3:
score: 0
Accepted
time: 2246ms
memory: 136708kb
input:
8 IFSXA >><<= ZAKDA <>=>= UZVAA <<<>= MTACA <>>>= RJKVA <><<= IOXOA >=<<= MRMHA ><<<= BYFWA ==<>=
output:
0 16 108 396 816 720 0 0
result:
ok 8 numbers
Test #4:
score: 0
Accepted
time: 2186ms
memory: 134720kb
input:
8 BRKPR ><=<> VUCTO <<=<= PTCDB <<=>> PHMGV <><>< FGWHD >><>> SUSFH <<<<> IOLDD <<<<> WJPXX <><<<
output:
0 14 120 444 744 360 0 0
result:
ok 8 numbers
Test #5:
score: 0
Accepted
time: 2247ms
memory: 134728kb
input:
10 UAVZE =>=<= QVGJB >==>> ZLHUS >>>=> PGZOO ==<>< LAKYL =<=<= IMQAQ <>>== OBWGV >>=<> KQSOR <<>>= KGFVD >=<== RFDGJ <>><>
output:
2 66 48 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 2258ms
memory: 136716kb
input:
10 GOMVB >>>>< DSPSI =><== UKTNW <<>=< SKNLH >=<>< TNYRS =<<>< QZHXW <==>> NLWVU ><=>= WHBAI ><>>= QXDIC <=<>> JBUFE =>==<
output:
0 86 32 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 2251ms
memory: 134796kb
input:
10 SBDSY >>>=> NSYAP <><>= PIFGA >=>=> URDJY <>>>< EDLLY =><<> ZLWTD >>>>= OTTLU <><=< HYKKZ ===<< VRBUB =<><> AXKEY <==<>
output:
2 60 90 42 0 0 0 0 0 0
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 2055ms
memory: 134800kb
input:
10 CPIAM ><>>> FZBGT ><>>> EUFKN ><>=> OWUOO <<<<> RJOOA <>><> VOMTV <<><= FZAYC ><><> GOQML ><><> WZGOV <<><= AAAAA <<<<<
output:
1 9 72 504 3024 15120 60480 181440 362880 362880
result:
ok 10 numbers
Test #9:
score: 0
Accepted
time: 2086ms
memory: 134672kb
input:
10 MYAFR <<>=< UUOJK <<><> AWYJM ><=<> FOSPK ><><> TUUIA <<><> OJAMS <>><< BUEGG ><>>> PTDUK <<><> SBLYM <>><> SFAAX >>>==
output:
0 14 128 816 4344 19320 65520 146160 161280 0
result:
ok 10 numbers
Test #10:
score: 0
Accepted
time: 2051ms
memory: 134640kb
input:
10 QJQVM <>>>< NYNHE ><>>< WSBQB <<>>> ONXCP <<<>< CKICH >>>>< CQHZL >>><< SPKWY <<<<< FAXVS >><<< RVBOC <<><> TRPLG =>>==
output:
0 28 250 1146 2856 3000 0 0 0 0
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 2046ms
memory: 134636kb
input:
10 PDOHN <>>>< YIBBD <>>>< VKHGC <><>> KLJOB ><>>> DIUHJ >>=>< AGDCK ><>>> FFXBK >><>< CHIEL ><>>> HGPXS >>><< GFHRX =>>=<
output:
0 38 230 822 2040 3480 2880 0 0 0
result:
ok 10 numbers
Test #12:
score: 0
Accepted
time: 2077ms
memory: 134796kb
input:
10 BWSGL ><<>> XEXGK <><>> OUHKP <>>=< ZWXCT <><>< VWAOX ><><< KXAHA ><>>> VVFUL ><<<> RHBTD >>><> FHBMB >>=<> JKVSX >==>>
output:
0 32 242 930 2424 5160 5760 0 0 0
result:
ok 10 numbers
Test #13:
score: 0
Accepted
time: 2121ms
memory: 134720kb
input:
10 TFXCY >><<< ALEDI ><>>> YBXWE <><<> YVCHH <<>>< JCYDR ><=>< GNURG ><<<< QFLEM <>>>> JUUHR ><><< LMDZE ><><< TEDEE >>=><
output:
0 46 268 564 144 0 0 0 0 0
result:
ok 10 numbers
Test #14:
score: 0
Accepted
time: 19558ms
memory: 136792kb
input:
100000 BNLGH >>=== QXYTZ >>=>> NRBRX <==== HSKHN <<>>> WPOWG >===> UXFEU =><>> GROWO =><>> VPKSO <><>< WKUQA ===>> KGKHU >=>>> YSIHF >=>>< TOSXN <=>=< HTCKZ =>=>= LIDLA >==>= MNVDK <<<=> WHGMQ ><>>= BRCSN ><<>> YLOEF <<==> IBVUP <><== JHWHE <==>> CBSKF >==>= OLGHJ <>><< OUDND =>==< AMFMU =<=== SDUHG...
output:
12144 412636794 259958531 471914400 521830768 776198196 987954473 677670949 929976028 435141791 915818255 77808332 373696275 860004456 815590598 827302790 334750217 297638785 684154009 734333884 468372005 941077614 669579770 347535008 712117434 881704206 973579427 385468207 664289497 158009373 53637...
result:
ok 100000 numbers
Test #15:
score: 0
Accepted
time: 19538ms
memory: 135428kb
input:
100000 YZHMP ><<== WTMOD <>><< RPZJR >=>=< AAJNC ===>= DIHKN =><>< ANVCM <<><= GLDOE <><=> KSNER <>>== WRKUF =<<>< ESGBH =><=< QTAKH <>=>< JGOSQ ><<<= MYSQR =>>== KLRPC =<=>< QRMKD ===== FCBZE >>>=< BNXDB =><=> NNRQD >==== BPVWI ==<=< KXEYZ ===>< IJMLR ==<>< ZGHZX =<=>< NDLJA <=<<< NOVNI ><<<< JKSRM...
output:
12223 400459039 28986202 438885749 273376351 163951784 446281085 40534769 335228183 96236785 880355311 987490628 488442137 827131227 536678086 420675015 209408414 489894579 26613846 266498745 429205709 284226414 110233883 328154083 561800066 269995982 113946391 76900398 905441256 821243833 20626991 ...
result:
ok 100000 numbers
Test #16:
score: 0
Accepted
time: 19539ms
memory: 135516kb
input:
100000 UNCSX <<==< FOYMG =<==< WQXDL <=<>= RKJSP <=>>= LAXXT ><<== IEMZF ==><= DFSET >=><= CWRSU <<>== XBCYM ><=>< YFAWT >><=< HTRNJ <<<>> ZWKMT ===>= QDLYL <<=<< JOFQE ==<>> SWETU <<><> MYVMS =<>=< DGRNR =<>>< CNXBA <<<>= WDWYZ =<>>> KPNNU >=>=< QTGOB ==<>< JCHUK ><=== MLTEW =<>=> DTMMV =<=>= BSPZQ...
output:
12256 398686308 110275411 25618548 98398475 75789291 450067286 554959802 735917475 608870282 245681817 893103261 540261582 229311537 936917938 470322306 441117213 243813087 255324265 12696724 854288754 806520692 86012500 328564694 878537022 839751145 915142745 18140745 125518575 342802686 947890980 ...
result:
ok 100000 numbers
Test #17:
score: 0
Accepted
time: 19976ms
memory: 136848kb
input:
100000 FNVIO ><<=< ISCUB ><><> GQCGY ><>>< IIREF ><>>> LAWQL >><<< VDQNS <>><< ZDJDH <>>>= KAYMX >><<< KQWNL ><<<< MWVRW ><<<< FETOJ >=><< LEEOT >=><< ZGJPH <<><= VDPHC <>>>> VJRWA <<><> SCRPJ <>><< JBQCF >>>>> YWVGU <<<>< XGWNB <<<<> BTAWV ><><< RSMBD <<>>> KFBJX ><><< GPSZZ ><><< WMSOJ <<><< QLXDF...
output:
1 99999 17256472 629188600 994653422 292821735 911451747 83353224 313471011 405421054 346258483 928805941 779780412 28863579 29385371 263188556 923438024 483744622 815893954 359620773 119778186 363999506 944722253 608984733 934576938 654424456 495668524 619666932 294467430 975718913 171023568 124035...
result:
ok 100000 numbers
Test #18:
score: 0
Accepted
time: 20061ms
memory: 136764kb
input:
100000 LMPEM >>>>< TOLDK >>>>< JRYKL >=<>< WRTSU ==<=< TZPGR <<<>< BHJXB >><<> RABOA <>><> TXPJU ><>>< YVFBJ <<=>< NHATH >>><< CNZDF >><>= VHJJY >>>>< DOUAS >><>< GMMQA >><<> AMKPR >>>>< IKAET >>>>< MFRKW <><<< SSMLJ <<<<< YAMZX <><<< CCXTO >><<< QNAAD <>>>> XDHLM <>>>< BKGQR >>>>< UXXOM ><<>< ANGIJ...
output:
0 933308107 299928578 143136372 376251907 975068160 721593698 753716245 898914068 490205891 886874629 146781702 587935621 279193639 699856836 561537033 880030199 518890130 56000918 362873285 264834282 611906519 200388605 960190510 691501587 606436430 881745603 751535317 348317466 237651997 812697060...
result:
ok 100000 numbers
Test #19:
score: 0
Accepted
time: 19923ms
memory: 136716kb
input:
100000 GKZXQ >><<< KHLZG <><<> XOPSL <><<< BAIDJ >><<< ARFUW >=<<< SRWMZ ><<>< IXTCI ><<>> CUFJQ ><<<< POBFV ><>>= XZCXW <<<<< NYEWD ><><> CWOQS ><<>> VILXN >><<> AYMDC ><<<> MBCPI >>>>> CFRWC >><<> CXNGB ><<<> QNFZL ><><> PIGHX <><<< UUKUR <<<<< TUDZQ ><><> GILEV >><>= EGTTE >><<> RSKCL ><<>> LYCDJ...
output:
0 166507515 459156293 304072419 460723604 974806918 569354203 431542442 512958995 436405304 696400930 642914783 541251712 836652606 565059619 514610302 346747578 937985955 592127812 100884846 134893017 448171682 583736771 651700927 454623153 163064670 98018215 70402567 66918097 107584460 749714113 1...
result:
ok 100000 numbers
Test #20:
score: 0
Accepted
time: 20008ms
memory: 134896kb
input:
100000 BILQU ><><< EBKTE >><<> NKHCI <<>>> GKVMX >><<< GIWIC ><<<> MAJDU >>=>< YULTQ <<><< KUVIK ><<>> FHYGI >><>> JOFAK >=>>> WHJPB <=><> MOSVM >=<<> MDBWH <>><> VLLQC <<><> YQTQA <<<<> VZJNK <<><= TNHBE <>>>> OHYMP >><<> FQAOU ><><< LNWSW >><<< VBFVF <>><> OMQUC >><<> HCIUP >>><> MMZQH >><<> YJZWL...
output:
0 38401793 447045659 902564881 855486954 858682963 916341122 319325485 19812241 668526803 143151417 331148639 425925192 804865129 333676787 704794449 910479352 696417420 82040052 29985024 973090487 9476047 487918272 830170804 447737654 497561219 593481691 928465739 179957021 384533495 178611683 4766...
result:
ok 100000 numbers
Test #21:
score: 0
Accepted
time: 19959ms
memory: 135520kb
input:
100000 KSHEU ><><< LUTYV ><<<< MXQOI ><<>> NNMHY ><><< NZIPQ ><><< XMKMH <><>> DDFVV >>><< TMRIN <<><< YDSBB ==<>> GEIFO >><>< JRWVV ><<<< LXVTF ><<>> KFCQQ >>><< TVKCO ><<>< OHAGB >>><= PEVCO ><<>< LYCEB ><>>> NNNTN ><<>< EYYBZ ><<>< MPCCW ><>>< HTJKP ><><< LQQDT ><<>< WBTLI >><>= JRYTE ><<>> POITD...
output:
0 964094440 836003257 708459847 871957496 654344326 948234133 953935212 104979316 364845725 665219506 642340940 870161743 128194009 326925049 353939789 704216254 589740748 620536805 305640004 484148956 831968196 6769193 754098116 546127667 437282971 570088555 466566847 739533250 638265014 473500063 ...
result:
ok 100000 numbers
Test #22:
score: 0
Accepted
time: 19996ms
memory: 135504kb
input:
100000 IMBCQ <<>>> SLSQD <<<=> AEBES >>>>< HTEYK ><><> BRSCG ><<>> LDIEX <<><< BMEJV ><<>< LCKFQ <><>> IPIDE =<>=> IPSKI ><>>> IYLZC =<><> EOQKE ><>>> EAOOD >>=<> XGZUO <><<= RAVYT <><<< EVMYK ><><> GWXYP <<<<> UEVNV <><=< AQQOY ><><< NRJDS <<<>= HCNOG <><>> SULRW <<><< FXNYW ><><< NEJQZ <><=< LYWGI...
output:
0 666826810 289231209 635258529 546720275 543561692 384443596 63424828 510070428 21542771 129058559 151021435 187384460 692633074 922852987 414682697 568116010 769155697 91852932 392144234 495241700 671207649 143169942 467816836 792533501 612880812 687987052 299606463 754344297 139546526 882788940 4...
result:
ok 100000 numbers
Test #23:
score: 0
Accepted
time: 19993ms
memory: 135396kb
input:
100000 FNFJC >=>>> JBTYS >>=<< QVCYB <<><> TTGOO <>>>> CNNNE >=<<= HCQEM >>><< KTESX ><><< RLPVL <>><> CQADI ><><< NCZRF <><<> NTWBK <><>> OJUNY <>><< MHIDY >>>>< LFECL >>>>< ENNVS >=<<< YYXYK <<<<> BALXT >>><> JVXBJ ><<>< PTDBE ><>>> RCFNT <>><> ZPWFG <<=>> MSVDA ><<<> YJXSV <><<< DOVKD ><<>> DXSPO...
output:
0 93009970 219804152 844567284 891926848 279947250 689135271 860615218 13010915 929722006 847603974 484303861 136418364 827768488 46032089 429102220 810639676 270957951 53183964 293737892 477650398 234505706 517796197 156812171 966975447 945982240 982711670 726121039 576777787 297259995 372223803 55...
result:
ok 100000 numbers
Test #24:
score: 0
Accepted
time: 19993ms
memory: 135516kb
input:
100000 TPOQJ <<<<> XUUDN <<<>< YFAGQ <>>>< VWSWT <<<<> GITXC <><<< AYRDP ><>>< ZOXOZ <=>>= OQEEJ >>>>> LMMFK <>>>< YQMTZ <>=<< BAWDI >><>> TQUIE <><>> LQFOZ ><<<= XYJNB ><>>> ANPKA ><<>> XNAGO <>>>> AARCV >>>=> IMBOU <>><< ECQGU =><>< EWFDL <<<>> AFWTZ >>><< FKLNJ =><>< CEPMR >><<= DPBFC ><><> YIHUM...
output:
0 731820826 161250844 5585597 470134782 556060811 257099719 111798459 512206035 622445488 559050664 46611111 378388720 149248369 900197806 243792137 756773235 70170364 529089164 538199381 933788591 643539872 670120393 985010776 935645389 262590905 309790899 412774006 752230002 629492948 403174711 17...
result:
ok 100000 numbers
Test #25:
score: 0
Accepted
time: 19977ms
memory: 135584kb
input:
100000 QBQZL <><<> DLOQX ><<<< QFGSH >>>>> GXSNZ ><<<< RDDUT <>>=< WXVWY <<<=< VCCQL <>>=> YSTQR <<>=< DFUIN =><>< GEGVJ <>><< SDHHM >><>> HQFRU >><>< ZHMPJ <<=>> TVMYN ><><< RCXHI <><>> CIYCA >><<> KVATT <<>>< GUWBK <<<>> EUUKP ><<>> BHKJW >><<< XAIMU <>><> LBYQV >><>= FKLSD >>><> VUQIB <<<<> ATMAS...
output:
0 646701422 310542475 455998428 727671893 716649694 854302830 116778947 413591563 630505272 957959940 707160196 798797072 884778819 315551957 165825483 211983439 44654126 489986563 445117918 290339951 363429453 357974679 236558197 5060958 200582726 105877545 962523756 472161796 650269082 123320504 8...
result:
ok 100000 numbers
Test #26:
score: 0
Accepted
time: 2266ms
memory: 132724kb
input:
1 ZZZZZ =>=>>
output:
1
result:
ok 1 number(s): "1"