QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#668064 | #5576. Advertising ICPC | enze114514 | TL | 1ms | 3604kb | C++20 | 3.8kb | 2024-10-23 11:01:53 | 2024-10-23 11:02:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
ll powmod_func(ll a, ll b) {
ll res = 1;
a %= MOD;
while(b > 0){
if(b & 1){
res = res * a % MOD;
}
a = a * a % MOD;
b >>= 1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> grid(n);
for(int i=0; i<n; i++) cin >> grid[i];
int k = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(grid[i][j] == '?') k++;
}
}
bool has_pre_filled_pattern = false;
for(int i=0; i<n-1 && !has_pre_filled_pattern; i++) {
for(int j=0; j<m-1 && !has_pre_filled_pattern; j++) {
if(grid[i][j] != '?' && grid[i][j+1] != '?' && grid[i+1][j] != '?' && grid[i+1][j+1] != '?'){
if(grid[i][j] == 'I' && grid[i][j+1] == 'C' && grid[i+1][j] == 'P' && grid[i+1][j+1] == 'C'){
has_pre_filled_pattern = true;
}
}
}
}
ll T = powmod_func(3, k);
if(has_pre_filled_pattern){
cout << T % MOD;
return 0;
}
int pow3_m = 1;
for(int i=0; i<m; i++) pow3_m *= 3;
vector<vector<int>> allowed_states(n, vector<int>());
for(int r=0; r<n; r++){
for(int s=0; s<pow3_m; s++){
bool valid = true;
int temp = s;
for(int j=0; j<m; j++){
int val = temp % 3;
temp /= 3;
if(grid[r][j] != '?'){
if((grid[r][j] == 'C' && val != 0) ||
(grid[r][j] == 'I' && val != 1) ||
(grid[r][j] == 'P' && val != 2)){
valid = false;
break;
}
}
}
if(valid){
allowed_states[r].push_back(s);
}
}
}
vector< vector< vector<int> > > row_digits(n, vector< vector<int> >(pow3_m, vector<int>(m, 0)));
for(int r=0; r<n; r++){
for(auto &s: allowed_states[r]){
int temp = s;
for(int j=0; j<m; j++){
row_digits[r][s][j] = temp % 3;
temp /= 3;
}
}
}
vector< vector< vector<int> > > transitions(n-1, vector< vector<int> >(pow3_m, vector<int>()));
for(int r=1; r<n; r++){
for(auto &s_prev: allowed_states[r-1]){
for(auto &s_curr: allowed_states[r]){
bool forbidden = false;
for(int j=0; j<m-1; j++){
if(row_digits[r-1][s_prev][j] == 1 &&
row_digits[r-1][s_prev][j+1] == 0 &&
row_digits[r][s_curr][j] == 2 &&
row_digits[r][s_curr][j+1] == 0){
forbidden = true;
break;
}
}
if(!forbidden){
transitions[r-1][s_prev].push_back(s_curr);
}
}
}
}
vector<ll> dp_prev(pow3_m, 0);
for(auto &s: allowed_states[0]){
dp_prev[s] = 1;
}
for(int r=1; r<n; r++){
vector<ll> dp_curr(pow3_m, 0);
for(auto &s_prev: allowed_states[r-1]){
if(dp_prev[s_prev] == 0) continue;
for(auto &s_curr: transitions[r-1][s_prev]){
dp_curr[s_curr] = (dp_curr[s_curr] + dp_prev[s_prev]) % MOD;
}
}
dp_prev = dp_curr;
}
ll A = 0;
for(auto &s: allowed_states[n-1]){
A = (A + dp_prev[s]) % MOD;
}
ll answer = (T - A + MOD) % MOD;
cout << answer;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3536kb
input:
3 3 ??? ?I? ???
output:
243
result:
ok single line: '243'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
2 2 IC PC
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Time Limit Exceeded
input:
8 8 ???????? ???????? ???????? ???????? ???????? ???????? ???????? ????????