QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#82562#5576. Advertising ICPCYanagi_OrigamiAC ✓22ms12668kbC++143.0kb2023-02-28 05:54:252023-02-28 05:54:27

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-28 05:54:27]
  • 评测
  • 测评结果:AC
  • 用时:22ms
  • 内存:12668kb
  • [2023-02-28 05:54:25]
  • 提交

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'