QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#181494#5576. Advertising ICPCFYBGCWA 2ms7344kbC++143.4kb2023-09-16 19:44:182023-09-16 19:44:19

Judging History

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

  • [2023-09-16 19:44:19]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7344kb
  • [2023-09-16 19:44:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 20, P = 998244353;
    
int n, m;
int a[N][N], b[N][N];
char g[N][N];
int Corways[N][N][N][N];
int WOICPC[N][N][N][N];
int allways[N][N][N][N];

int solve(int x1, int y1, int x2, int y2);

int qmi(int m, int k)
{
    int res = 1, t = m;
    while(k)
    {
        if(k & 1)
            res = (res * t) % P;
        k >>= 1;
        t =  t * t % P;
    }
    return res;
}


int get_ways(int x1, int y1, int x2, int y2)
{    
    if(x1 <= x2 && y1 <= y2 && x1 > 0 && x2 > 0 && y1 > 0 && y2 > 0 && x1 <= n && x2 <= n && y1 <= m && y2 <= m);
    else return 1;
    if(allways[x1][y1][x2][y2] == -1);
    {
        int num = b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1];
        allways[x1][y1][x2][y2] = qmi(3, num);
    }
    return allways[x1][y1][x2][y2];
}

bool is_ICPC(int x1, int y1)
{
    if(x1 + 1 > n || y1 + 1 > m)    
        return 0;

    if((g[x1][y1] == 'I' || g[x1][y1] == '?') && (g[x1][y1 + 1] == 'C' || g[x1][y1 + 1] == '?') && (g[x1 + 1][y1] == 'P' || g[x1 + 1][y1] == '?') && (g[x1 + 1][y1 + 1] == 'C' || g[x1 + 1][y1 + 1] == '?'))
        return 1;
    return 0;
}

int without_ICPC(int x1, int y1, int x2, int y2)
{
    if(x1 <= x2 && y1 <= y2 && x1 > 0 && x2 > 0 && y1 > 0 && y2 > 0 && x1 <= n && x2 <= n && y1 <= m && y2 <= m);
    else return 1;

    if(WOICPC[x1][y1][x2][y2] != -1)
        return WOICPC[x1][y1][x2][y2];
    
    WOICPC[x1][y1][x2][y2] = ((get_ways(x1, y1, x2, y2) - solve(x1, y1, x2, y2) ) %P + P) % P;
    return WOICPC[x1][y1][x2][y2];
}

int solve(int x1, int y1, int x2, int y2)
{
    if(x1 <= x2 && y1 <= y2 && x1 > 0 && x2 > 0 && y1 > 0 && y2 > 0 && x1 <= n && x2 <= n && y1 <= m && y2 <= m);
    else return 0;

    if(Corways[x1][y1][x2][y2] != -1)
        return Corways[x1][y1][x2][y2];
    
    if(x2 - x1 + 1 == 2 && y2 - y1 + 1 == 2)
    {
        if(is_ICPC(x1, y1))
            return 1;
        return 0;
    }

    if(x2 - x1 + 1 < 2 || y2 - y1 + 1 < 2)
        return 0;
    
    int res = 0;

    for(int i = x1; i < x2; i++)
        for(int j = y1; j < y2; j++)
        {
            if(is_ICPC(i, j))
            {
                int part1 = without_ICPC(x1, y1, i, y2) * without_ICPC(x1, y1, i + 1, j - 1) % P * qmi(without_ICPC(x1, y1, i, j - 1), P - 2) % P; 
                if(g[i][j] == '?' )
                	part1 = part1 * qmi(3, P - 2) % P;
                if(g[i][j + 1] == '?' )
                	part1 = part1 * qmi(3, P - 2) % P;
                	
				int part2 = get_ways(i + 1 , j + 2, i + 1, y2) * get_ways(i + 2, y1, x2, y2) % P; 
//                cerr << without_ICPC(x1, y1, i, j - 1) << ' ' << part2 << '\n';
				res = ((part1 * part2 % P) + res) % P;
            }
        }

    Corways[x1][y1][x2][y2] = res;

    return res;
}

signed main()
{
    cin >> n >> m;
    memset(Corways, -1, sizeof Corways);
    memset(WOICPC, -1, sizeof WOICPC);
    memset(allways, -1, sizeof allways);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            cin >> g[i][j];
            if(g[i][j] == '?')
                a[i][j] = 1;    
        }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i-1][j-1] + a[i][j];
    
    cout << solve(1, 1, n, m) << '\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 7344kb

input:

3 3
???
?I?
???

output:

243

result:

ok single line: '243'

Test #2:

score: 0
Accepted
time: 1ms
memory: 7300kb

input:

2 2
IC
PC

output:

1

result:

ok single line: '1'

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 7168kb

input:

8 8
????????
????????
????????
????????
????????
????????
????????
????????

output:

81904862

result:

wrong answer 1st lines differ - expected: '776529021', found: '81904862'