QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117773#5576. Advertising ICPCrania__AC ✓19ms42672kbC++143.1kb2023-07-02 06:52:592023-07-02 06:53:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-02 06:53:01]
  • 评测
  • 测评结果:AC
  • 用时:19ms
  • 内存:42672kb
  • [2023-07-02 06:52:59]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'