QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#668069 | #5576. Advertising ICPC | enze114514 | TL | 1ms | 3728kb | C++20 | 3.1kb | 2024-10-23 11:05:17 | 2024-10-23 11:05:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
ll pow3(int k) {
ll res = 1;
ll base = 3;
while(k > 0){
if(k & 1){
res = res * base % MOD;
}
base = base * base % MOD;
k >>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> grid(n);
int k =0;
for(int i=0;i<n;i++) {
cin >> grid[i];
for(int j=0;j<m;j++) if(grid[i][j] == '?') k++;
}
int total_states = pow(3, m);
vector<int> allowed_states(n);
vector<vector<int>> states_per_row(n);
vector<vector<int>> state_cells(n, vector<int>(total_states * m, 0));
for(int r=0;r<n;r++){
for(int s=0;s<pow(3, m);s++){
bool valid = true;
int tmp = s;
for(int j=0;j<m;j++){
int val = tmp %3;
tmp /=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;
}
}
state_cells[r][s * m + j] = val;
}
if(valid){
states_per_row[r].push_back(s);
}
}
}
vector<vector<vector<int>>> transitions(n, vector<vector<int>>(pow(3, m), vector<int>()));
for(int r=1;r<n;r++){
for(auto s_prev : states_per_row[r-1]){
for(auto s_curr : states_per_row[r]){
bool forbidden = false;
for(int j=0; j<m-1 && !forbidden; j++){
int cell_prev_j = (s_prev / (int)pow(3, j)) %3;
int cell_prev_j1 = (s_prev / (int)pow(3, j+1)) %3;
int cell_curr_j = (s_curr / (int)pow(3, j)) %3;
int cell_curr_j1 = (s_curr / (int)pow(3, j+1)) %3;
if(cell_prev_j ==1 && cell_prev_j1 ==0 && cell_curr_j ==2 && cell_curr_j1 ==0){
forbidden = true;
break;
}
}
if(!forbidden){
transitions[r][s_prev].push_back(s_curr);
}
}
}
}
vector<ll> dp_prev(pow(3, m), 0);
for(auto s : states_per_row[0]){
dp_prev[s] =1;
}
for(int r=1;r<n;r++){
vector<ll> dp_curr(pow(3, m), 0);
for(auto s_prev : states_per_row[r-1]){
if(dp_prev[s_prev]==0) continue;
for(auto s_curr : transitions[r][s_prev]){
dp_curr[s_curr] = (dp_curr[s_curr] + dp_prev[s_prev]) % MOD;
}
}
dp_prev = move(dp_curr);
}
ll A =0;
for(auto s : states_per_row[n-1]){
A = (A + dp_prev[s]) % MOD;
}
ll T = pow3(k);
ll answer = (T - A + MOD) % MOD;
cout << answer;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3728kb
input:
3 3 ??? ?I? ???
output:
243
result:
ok single line: '243'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
2 2 IC PC
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Time Limit Exceeded
input:
8 8 ???????? ???????? ???????? ???????? ???????? ???????? ???????? ????????