QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#117773 | #5576. Advertising ICPC | rania__ | AC ✓ | 19ms | 42672kb | C++14 | 3.1kb | 2023-07-02 06:52:59 | 2023-07-02 06:53:01 |
Judging History
answer
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 7, P1 = 31, P2 = 37, mod =998244353;
int mul(int a, int b) {
return (1LL * a * b) % mod;
}
int add(int a, int b) {
a = (a + mod) % mod;
b = (b + mod) % mod;
return (a + b) % mod;
}
int fp(int b, int p) {
if (b == 1 or p == 0)
return 1;
int ret = fp(b, p >> 1);
ret = mul(ret, ret);
if (p & 1)
ret = mul(ret, b);
return ret;
}
ll modInv(ll n) {
return fp(n, mod - 2);
}
ll fact[N], inv[N];
void pre() {
fact[0] = inv[0] = 1;
for (ll i = 1; i < N; i++)
fact[i] = (fact[i - 1] * i) % mod, inv[i] = fp(fact[i], mod - 2);
}
ll nCr(ll n, ll r) {
return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;
}
ll nPr(ll n, ll r) {
return ((fact[n] * inv[n - r])) % mod;
}
int n, m;
char arr[255][255];
int dp[8 * 8 + 8][(1 << 8) + 1][(1 << 8) + 1][2];
int solve(int i, int j, int maski, int maskp, bool found) {
if (i == n)
return found;
if (j >= m) // row gded
{
return solve(i + 1, 0, maski, maskp, found);
}
int idx = (i * m + j);
int &ret = dp[idx][maski][maskp][found];
if (~ret)
return ret;
ret = 0;
int nwi = maski;
int nwp = maskp;
nwi &= ~(1 << (j));
nwp &= ~(1 << (j));
//7ot i
if ((arr[i][j] == 'I' || arr[i][j] == '?')) {
ret = add(ret, solve(i, j + 1, nwi | (1 << j), nwp, found));
}
//7ot p
if ((arr[i][j] == 'P' || arr[i][j] == '?')) {
ret = add(ret, solve(i, j + 1, nwi, nwp | (1 << j), found));
}
// c
if ((j + 1 < m) && (maski & (1 << (j))) && (maskp & (1 << (j + 1))) && (arr[i][j] == 'C' || arr[i][j] == '?') &&
(arr[i][j + 1] == 'C' || arr[i][j + 1] == '?')) {
//cc
nwi &= ~(1 << (j + 1));
nwp &= ~(1 << (j + 1));
ret = add(ret, solve(i, j + 2, nwi, nwp, 1));
if ( arr[i][j+1] == '?'){
//cp
ret = add(ret, solve(i, j + 2, nwi, nwp | (1 << (j+1)), found));
//ci
ret = add(ret, solve(i, j + 2, nwi | (1 << (j+1)), nwp, found));
}
} else if ((arr[i][j] == 'C' || arr[i][j] == '?')) {
ret = add(ret, solve(i, j + 1, nwi, nwp, found));
}
return ret;
}
void doWork() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> arr[j][i];
}
}
swap(m, n);
memset(dp, -1, sizeof dp);
cout << solve(0, 0, 0, 0, 0) << endl;
}
int main() {
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
// freopen("bisector.in","r",stdin);
// freopen("bisector.out","w",stdout);
int t = 1;
// cout << primes.size() << endl;
// cin >> t;
while (t--) {
doWork();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 42604kb
input:
3 3 ??? ?I? ???
output:
243
result:
ok single line: '243'
Test #2:
score: 0
Accepted
time: 8ms
memory: 41608kb
input:
2 2 IC PC
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 19ms
memory: 42032kb
input:
8 8 ???????? ???????? ???????? ???????? ???????? ???????? ???????? ????????
output:
776529021
result:
ok single line: '776529021'
Test #4:
score: 0
Accepted
time: 1ms
memory: 42408kb
input:
2 2 ?? ??
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 41764kb
input:
2 2 CP CI
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 4ms
memory: 40784kb
input:
2 2 IP CC
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 7ms
memory: 40792kb
input:
2 2 PI CC
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 0ms
memory: 41404kb
input:
2 2 CI CP
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 1ms
memory: 41264kb
input:
2 8 ???P???? ???P??P?
output:
115443
result:
ok single line: '115443'
Test #10:
score: 0
Accepted
time: 1ms
memory: 40716kb
input:
2 8 IC???C?? ?I?IC?I?
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1ms
memory: 41796kb
input:
2 8 ?????P?? I???C??I
output:
32562
result:
ok single line: '32562'
Test #12:
score: 0
Accepted
time: 4ms
memory: 40976kb
input:
2 8 ?PIC?CP? ?CIPC?IC
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 8ms
memory: 42392kb
input:
2 8 CCCPICPP PII?PCCP
output:
3
result:
ok single line: '3'
Test #14:
score: 0
Accepted
time: 4ms
memory: 40976kb
input:
8 2 P? ?? ?? ?? I? ?? ?P ??
output:
96957
result:
ok single line: '96957'
Test #15:
score: 0
Accepted
time: 1ms
memory: 41480kb
input:
8 2 ?? C? ?? ?? ?? ?? ?? I?
output:
234009
result:
ok single line: '234009'
Test #16:
score: 0
Accepted
time: 1ms
memory: 41848kb
input:
8 2 PI CC IC CI ?I P? CP CP
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 4ms
memory: 42396kb
input:
8 2 ?C II CC IP ?C C? PP ?I
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 1ms
memory: 40960kb
input:
8 2 PP PC ?I ?C II CC I? CI
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 1ms
memory: 41316kb
input:
3 8 ????I??? ???P???? ??????P?
output:
598932682
result:
ok single line: '598932682'
Test #20:
score: 0
Accepted
time: 1ms
memory: 41088kb
input:
3 8 ???C???? ???????C I???????
output:
176286317
result:
ok single line: '176286317'
Test #21:
score: 0
Accepted
time: 2ms
memory: 41568kb
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: 42620kb
input:
3 8 I?IPCCC? ?CPCC?P? ?CCPCC?I
output:
486
result:
ok single line: '486'
Test #23:
score: 0
Accepted
time: 0ms
memory: 41096kb
input:
3 8 CPICCCIP CIP??CPC CPPPCIPC
output:
4
result:
ok single line: '4'
Test #24:
score: 0
Accepted
time: 3ms
memory: 40780kb
input:
8 3 ??? ??? ??? ??? I?? ??? ?P? ???
output:
181529684
result:
ok single line: '181529684'
Test #25:
score: 0
Accepted
time: 4ms
memory: 42056kb
input:
8 3 I?? ??? I?? ?C? ??P ?I? CII C?C
output:
966654
result:
ok single line: '966654'
Test #26:
score: 0
Accepted
time: 0ms
memory: 42124kb
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: 3ms
memory: 42460kb
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: 4ms
memory: 40748kb
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: 7ms
memory: 40920kb
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: 0ms
memory: 42408kb
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: 40928kb
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: 0ms
memory: 41600kb
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: 42512kb
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: 18ms
memory: 41032kb
input:
8 7 ??????? ??????? ??????C ??????? ??????? ??????? ??????? ???????
output:
407572405
result:
ok single line: '407572405'
Test #35:
score: 0
Accepted
time: 0ms
memory: 41760kb
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: 40940kb
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: 4ms
memory: 41592kb
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: 1ms
memory: 40832kb
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: 7ms
memory: 42672kb
input:
7 8 ???????? ???????? ?P?????? ???????? ???????? ???????? ????????
output:
335862381
result:
ok single line: '335862381'
Test #40:
score: 0
Accepted
time: 4ms
memory: 40916kb
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: 40680kb
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: 41832kb
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: 41028kb
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: 4ms
memory: 41228kb
input:
7 7 ???C??? ??????? ??????? P?????P ??????? I?????C ???????
output:
45031736
result:
ok single line: '45031736'
Test #45:
score: 0
Accepted
time: 8ms
memory: 41536kb
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: 42084kb
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: 41724kb
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: 41520kb
input:
7 7 I?PPPPC CIIICPP CCCPPPP PP?PCIP IIIIIPI ICIPCII ?ICPPCI
output:
0
result:
ok single line: '0'