QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #753324 | #5576. Advertising ICPC | anyan26 | AC ✓ | 778ms | 90492kb | C++17 | 2.1kb | 2024-11-16 12:22:10 | 2024-11-16 12:22:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int main()
{
int n, m;
cin >> n >> m;
char grid[n][m];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> grid[i][j];
}
}
map<string, int> dp[n][m];
if(grid[0][0]=='I' || grid[0][0]=='?')dp[0][0]["I"] = 1;
if(grid[0][0]=='C' || grid[0][0]=='?')dp[0][0]["C"] = 1;
if(grid[0][0]=='P' || grid[0][0]=='?')dp[0][0]["P"] = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if(i==0 && j==0)continue;
for (auto &mask : dp[i][(j - 1)%m])
{
if(grid[i][j]=='I' || grid[i][j]=='?'){
string cur = mask.first + "I";
if(cur.size() > (m+1))cur = cur.substr(1);
dp[i][j][cur] += mask.second;
dp[i][j][cur] %= mod;
}
if(grid[i][j]=='P'||grid[i][j]=='?'){
string cur = mask.first + "P";
if(cur.size() > (m+1))cur = cur.substr(1);
dp[i][j][cur] += mask.second;
dp[i][j][cur] %= mod;
}
if (grid[i][j] == 'C' || grid[i][j]=='?')
{
if (mask.first.size() == (m+1) &&
mask.first[0] == 'I' && mask.first[1] == 'C' && mask.first[m] == 'P'
&& j != 0)
{
continue;
}
string cur = mask.first + "C";
if(cur.size() > (m+1))cur = cur.substr(1);
dp[i][j][cur] += mask.second;
dp[i][j][cur] %= mod;
}
}
}
}
long long ret = 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j]=='?')ret *= 3;
ret %= mod;
}
}
for(auto & i : dp[n-1][m-1]){
ret -= i.second;
ret %= mod;
}
cout << (ret+mod)%mod << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
3 3 ??? ?I? ???
output:
243
result:
ok single line: '243'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
2 2 IC PC
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 778ms
memory: 90492kb
input:
8 8 ???????? ???????? ???????? ???????? ???????? ???????? ???????? ????????
output:
776529021
result:
ok single line: '776529021'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
2 2 ?? ??
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
2 2 CP CI
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
2 2 IP CC
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
2 2 PI CC
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
2 2 CI CP
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 18ms
memory: 6940kb
input:
2 8 ???P???? ???P??P?
output:
115443
result:
ok single line: '115443'
Test #10:
score: 0
Accepted
time: 2ms
memory: 4008kb
input:
2 8 IC???C?? ?I?IC?I?
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 4ms
memory: 5104kb
input:
2 8 ?????P?? I???C??I
output:
32562
result:
ok single line: '32562'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
2 8 ?PIC?CP? ?CIPC?IC
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
2 8 CCCPICPP PII?PCCP
output:
3
result:
ok single line: '3'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
8 2 P? ?? ?? ?? I? ?? ?P ??
output:
96957
result:
ok single line: '96957'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
8 2 ?? C? ?? ?? ?? ?? ?? I?
output:
234009
result:
ok single line: '234009'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
8 2 PI CC IC CI ?I P? CP CP
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3804kb
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: 3648kb
input:
8 2 PP PC ?I ?C II CC I? CI
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 69ms
memory: 13656kb
input:
3 8 ????I??? ???P???? ??????P?
output:
598932682
result:
ok single line: '598932682'
Test #20:
score: 0
Accepted
time: 62ms
memory: 12344kb
input:
3 8 ???C???? ???????C I???????
output:
176286317
result:
ok single line: '176286317'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
3 8 ?IPCI??I ?C?CIIP? ?PCP?P?C
output:
0
result:
ok single line: '0'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
3 8 I?IPCCC? ?CPCC?P? ?CCPCC?I
output:
486
result:
ok single line: '486'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
3 8 CPICCCIP CIP??CPC CPPPCIPC
output:
4
result:
ok single line: '4'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3936kb
input:
8 3 ??? ??? ??? ??? I?? ??? ?P? ???
output:
181529684
result:
ok single line: '181529684'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
8 3 I?? ??? I?? ?C? ??P ?I? CII C?C
output:
966654
result:
ok single line: '966654'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3640kb
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: 0ms
memory: 3544kb
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: 3648kb
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: 234ms
memory: 35256kb
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: 52ms
memory: 11468kb
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: 7ms
memory: 5144kb
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: 1ms
memory: 3720kb
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: 1ms
memory: 3904kb
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: 185ms
memory: 26184kb
input:
8 7 ??????? ??????? ??????C ??????? ??????? ??????? ??????? ???????
output:
407572405
result:
ok single line: '407572405'
Test #35:
score: 0
Accepted
time: 12ms
memory: 6312kb
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: 3ms
memory: 4888kb
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: 3744kb
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: 0ms
memory: 3620kb
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: 589ms
memory: 68932kb
input:
7 8 ???????? ???????? ?P?????? ???????? ???????? ???????? ????????
output:
335862381
result:
ok single line: '335862381'
Test #40:
score: 0
Accepted
time: 63ms
memory: 13912kb
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: 10ms
memory: 6500kb
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: 0ms
memory: 3908kb
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: 0ms
memory: 3576kb
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: 72ms
memory: 13932kb
input:
7 7 ???C??? ??????? ??????? P?????P ??????? I?????C ???????
output:
45031736
result:
ok single line: '45031736'
Test #45:
score: 0
Accepted
time: 9ms
memory: 5160kb
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: 1ms
memory: 3744kb
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: 1ms
memory: 3664kb
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: 0ms
memory: 3492kb
input:
7 7 I?PPPPC CIIICPP CCCPPPP PP?PCIP IIIIIPI ICIPCII ?ICPPCI
output:
0
result:
ok single line: '0'