QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#181494 | #5576. Advertising ICPC | FYBGC | WA | 2ms | 7344kb | C++14 | 3.4kb | 2023-09-16 19:44:18 | 2023-09-16 19:44:19 |
Judging History
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'