QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #82562 | #5576. Advertising ICPC | Yanagi_Origami | AC ✓ | 22ms | 12668kb | C++14 | 3.0kb | 2023-02-28 05:54:25 | 2023-02-28 05:54:27 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for(int i=a;i<=(b);i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int Mod=998244353;
char s[10][10];
int f[10][10][2][20005],n,m;
void Upd(int &x,int y){ x=(x+y)%Mod; }
int main(){
scanf("%d%d",&n,&m);
//puts("HERE");
rep(i,1,n) scanf("%s",s[i]+1);
int MAXS=1;
rep(i,1,m+1) MAXS*=3;
f[0][m][0][MAXS-1]=1;
rep(i,1,n){
rep(S,0,MAXS-1){
if(f[i-1][m][0][S]==0&&f[i-1][m][1][S]==0) continue;
//printf("## %d %d at %d\n",f[i-1][m][0][S],f[i-1][m][1][S],i-1);
if(s[i][1]=='?'){
rep(k,0,2){
Upd(f[i][1][0][S*3%MAXS+k],f[i-1][m][0][S]);
Upd(f[i][1][1][S*3%MAXS+k],f[i-1][m][1][S]);
//printf("%d -> %d : %d %d %d\n",S,S*3%MAXS+k,f[i][1][0][S*3%MAXS+k],i,1);
}
}
if(s[i][1]=='I'){
Upd(f[i][1][0][S*3%MAXS+0],f[i-1][m][0][S]);
Upd(f[i][1][1][S*3%MAXS+0],f[i-1][m][1][S]);
//printf("%d -> %d\n",S,S*3%MAXS+0);
}
if(s[i][1]=='C'){
Upd(f[i][1][0][S*3%MAXS+1],f[i-1][m][0][S]);
Upd(f[i][1][1][S*3%MAXS+1],f[i-1][m][1][S]);
//printf("%d -> %d\n",S,S*3%MAXS+1);
}
if(s[i][1]=='P'){
Upd(f[i][1][0][S*3%MAXS+2],f[i-1][m][0][S]);
Upd(f[i][1][1][S*3%MAXS+2],f[i-1][m][1][S]);
//printf("%d -> %d\n",S,S*3%MAXS+2);
}
}
rep(j,2,m){
rep(S,0,MAXS-1){
//if(S==0&&i==2&&j==3) printf("#@#@ %d\n",f[i][j-1][0][S]);
//if(S==0&&f[i][j-1][0][S]!=0) puts("HERE");
if(f[i][j-1][0][S]==0&&f[i][j-1][1][S]==0) continue;
if(s[i][j]=='?'){
rep(k,0,1){
Upd(f[i][j][0][S*3%MAXS+k*2],f[i][j-1][0][S]);
Upd(f[i][j][1][S*3%MAXS+k*2],f[i][j-1][1][S]);
//printf("sec %d -> %d\n",S,S*3%MAXS+k*2);
}
int x1=S%3,x2=S*3/MAXS,x3=(S*9/MAXS)%3;
if(x1==2 && x2==0 && x3==1){
Upd(f[i][j][1][S*3%MAXS+1],f[i][j-1][0][S]);
}else{
Upd(f[i][j][0][S*3%MAXS+1],f[i][j-1][0][S]);
}
Upd(f[i][j][1][S*3%MAXS+1],f[i][j-1][1][S]);
//printf("sec %d -> %d\n",S,S*3%MAXS+1);
//printf("@@@ %d %d %d %d\n",S,x1,x2,x3);
}
if(s[i][j]=='I'){
Upd(f[i][j][0][S*3%MAXS+0],f[i][j-1][0][S]);
Upd(f[i][j][1][S*3%MAXS+0],f[i][j-1][1][S]);
//puts("FUCK!");
//printf("sec %d -> %d : %d\n",S,S*3%MAXS+0,f[i][j][0][S*3%MAXS+0]);
}
if(s[i][j]=='C'){
int x1=S%3,x2=S*3/MAXS,x3=(S*9/MAXS)%3;
if(x1==2 && x2==0 && x3==1){
Upd(f[i][j][1][S*3%MAXS+1],f[i][j-1][0][S]);
}else{
Upd(f[i][j][0][S*3%MAXS+1],f[i][j-1][0][S]);
}
Upd(f[i][j][1][S*3%MAXS+1],f[i][j-1][1][S]);
//printf("sec %d -> %d\n",S,S*3%MAXS+1);
//printf("@@@ %d %d %d %d\n",S,x1,x2,x3);
}
if(s[i][j]=='P'){
Upd(f[i][j][0][S*3%MAXS+2],f[i][j-1][0][S]);
Upd(f[i][j][1][S*3%MAXS+2],f[i][j-1][1][S]);
//printf("%d -> %d\n",S,S*3%MAXS+2);
}
}
}
}
int ans=0;
rep(s,0,MAXS-1) Upd(ans,f[n][m][1][s]);
printf("%d",ans);
return 0;
}
/*
3 3
???
?I?
???
*/
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3832kb
input:
3 3 ??? ?I? ???
output:
243
result:
ok single line: '243'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
2 2 IC PC
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 22ms
memory: 12668kb
input:
8 8 ???????? ???????? ???????? ???????? ???????? ???????? ???????? ????????
output:
776529021
result:
ok single line: '776529021'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
2 2 ?? ??
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
2 2 CP CI
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
2 2 IP CC
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2 2 PI CC
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
2 2 CI CP
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4784kb
input:
2 8 ???P???? ???P??P?
output:
115443
result:
ok single line: '115443'
Test #10:
score: 0
Accepted
time: 3ms
memory: 4372kb
input:
2 8 IC???C?? ?I?IC?I?
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 3ms
memory: 4648kb
input:
2 8 ?????P?? I???C??I
output:
32562
result:
ok single line: '32562'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3912kb
input:
2 8 ?PIC?CP? ?CIPC?IC
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
2 8 CCCPICPP PII?PCCP
output:
3
result:
ok single line: '3'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
8 2 P? ?? ?? ?? I? ?? ?P ??
output:
96957
result:
ok single line: '96957'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
8 2 ?? C? ?? ?? ?? ?? ?? I?
output:
234009
result:
ok single line: '234009'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
8 2 PI CC IC CI ?I P? CP CP
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
8 2 ?C II CC IP ?C C? PP ?I
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
8 2 PP PC ?I ?C II CC I? CI
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 2ms
memory: 5740kb
input:
3 8 ????I??? ???P???? ??????P?
output:
598932682
result:
ok single line: '598932682'
Test #20:
score: 0
Accepted
time: 6ms
memory: 5696kb
input:
3 8 ???C???? ???????C I???????
output:
176286317
result:
ok single line: '176286317'
Test #21:
score: 0
Accepted
time: 1ms
memory: 4308kb
input:
3 8 ?IPCI??I ?C?CIIP? ?PCP?P?C
output:
0
result:
ok single line: '0'
Test #22:
score: 0
Accepted
time: 0ms
memory: 4376kb
input:
3 8 I?IPCCC? ?CPCC?P? ?CCPCC?I
output:
486
result:
ok single line: '486'
Test #23:
score: 0
Accepted
time: 3ms
memory: 3952kb
input:
3 8 CPICCCIP CIP??CPC CPPPCIPC
output:
4
result:
ok single line: '4'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3952kb
input:
8 3 ??? ??? ??? ??? I?? ??? ?P? ???
output:
181529684
result:
ok single line: '181529684'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3820kb
input:
8 3 I?? ??? I?? ?C? ??P ?I? CII C?C
output:
966654
result:
ok single line: '966654'
Test #26:
score: 0
Accepted
time: 2ms
memory: 3800kb
input:
8 3 CC? ??I ??? I?C PCC C?C ??C ??I
output:
241974
result:
ok single line: '241974'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
8 3 IIP ??? IPI P?C I?P P?C CPI C?P
output:
243
result:
ok single line: '243'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
8 3 PCP PPP ?CC CPP C?P CP? CPC II?
output:
0
result:
ok single line: '0'
Test #29:
score: 0
Accepted
time: 5ms
memory: 11044kb
input:
8 8 ???????? ?P??C?P? ???????? ????I??? ?P????I? ???C???? ???????? C??????I
output:
694454028
result:
ok single line: '694454028'
Test #30:
score: 0
Accepted
time: 9ms
memory: 8984kb
input:
8 8 ????I?PI ???PC?I? ????IPC? ?????P?? PPIC???? ?P????I? ???????C C?????C?
output:
943439945
result:
ok single line: '943439945'
Test #31:
score: 0
Accepted
time: 1ms
memory: 6740kb
input:
8 8 PPPI???? ??P??PIC ?PC??CCP CPP????I ?II????C CIPCI??C C??PPC?? PI?PCCCC
output:
930881552
result:
ok single line: '930881552'
Test #32:
score: 0
Accepted
time: 2ms
memory: 5020kb
input:
8 8 IPPI?IPP ICPC?II? IICII??I ?PPCPPCC ?C??I?II ?ICCCCCI PIIP?IIP ?P??II?C
output:
4782969
result:
ok single line: '4782969'
Test #33:
score: 0
Accepted
time: 4ms
memory: 4608kb
input:
8 8 PCPICCPP IIICIICI PCCPIC?P IIPICIIC CPIC?ICI PCCI?C?? C?CC?IIC CCPIPICP
output:
0
result:
ok single line: '0'
Test #34:
score: 0
Accepted
time: 3ms
memory: 6500kb
input:
8 7 ??????? ??????? ??????C ??????? ??????? ??????? ??????? ???????
output:
407572405
result:
ok single line: '407572405'
Test #35:
score: 0
Accepted
time: 1ms
memory: 5792kb
input:
8 7 ??????P ????P?? PC???C? P?P???? ?CI?P?? ?????PI ????C?? C?PCI?P
output:
299705028
result:
ok single line: '299705028'
Test #36:
score: 0
Accepted
time: 4ms
memory: 5292kb
input:
8 7 IP?I?I? ??C??C? IPC???? P???C?? ??IP??? IPI???C P??PPI? ?PPICCC
output:
945285612
result:
ok single line: '945285612'
Test #37:
score: 0
Accepted
time: 1ms
memory: 4568kb
input:
8 7 ?PCPC?C P?IC?P? P?ICPPC ?C??P?? P?PICPI I?CCC?I I??PCPI PCIIIPP
output:
24011073
result:
ok single line: '24011073'
Test #38:
score: 0
Accepted
time: 3ms
memory: 4364kb
input:
8 7 CIC??II CCIIPPC IPCIPCP IC?IPPI PPCCPP? ICPPIIP PPPCI?I CIICI??
output:
0
result:
ok single line: '0'
Test #39:
score: 0
Accepted
time: 8ms
memory: 11032kb
input:
7 8 ???????? ???????? ?P?????? ???????? ???????? ???????? ????????
output:
335862381
result:
ok single line: '335862381'
Test #40:
score: 0
Accepted
time: 3ms
memory: 8444kb
input:
7 8 CI?P?P?? I?P?I??? ??????I? ???PP??? ?C????P? ?P?????? ?PI?I??I
output:
371435886
result:
ok single line: '371435886'
Test #41:
score: 0
Accepted
time: 1ms
memory: 7224kb
input:
7 8 ICI?II?C ???C???? I?IC??I? ??CC???? C????CCI P??I??II C??I?PCP
output:
220669500
result:
ok single line: '220669500'
Test #42:
score: 0
Accepted
time: 2ms
memory: 5012kb
input:
7 8 CPI?CP?C I?P??PPI P?CCCPP? PIC?I?PP IPII?PII CIPCCP?? IIC???IP
output:
3483891
result:
ok single line: '3483891'
Test #43:
score: 0
Accepted
time: 1ms
memory: 4284kb
input:
7 8 IIICICII IIPPPCIP ICCP?C?C CPIP??IC IIICICII C?CPPPII CIPPCPCC
output:
243
result:
ok single line: '243'
Test #44:
score: 0
Accepted
time: 6ms
memory: 6040kb
input:
7 7 ???C??? ??????? ??????? P?????P ??????? I?????C ???????
output:
45031736
result:
ok single line: '45031736'
Test #45:
score: 0
Accepted
time: 1ms
memory: 5248kb
input:
7 7 ?P?C?I? ?????C? ??I?P?? ?CICPCC ???P??I IIPP?I? ???P???
output:
414440826
result:
ok single line: '414440826'
Test #46:
score: 0
Accepted
time: 2ms
memory: 4772kb
input:
7 7 ??I?P?C ?I?PIPC C???PPI I????PI PP?I?PC P?IIC?? IPC??CC
output:
623536432
result:
ok single line: '623536432'
Test #47:
score: 0
Accepted
time: 0ms
memory: 4572kb
input:
7 7 I??PCP? IPP?CCP IPIP?II P?CCPP? ?CP???P PPIC??C ??IPCPP
output:
1751787
result:
ok single line: '1751787'
Test #48:
score: 0
Accepted
time: 3ms
memory: 3980kb
input:
7 7 I?PPPPC CIIICPP CCCPPPP PP?PCIP IIIIIPI ICIPCII ?ICPPCI
output:
0
result:
ok single line: '0'