QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#668079 | #5576. Advertising ICPC | enze114514 | TL | 1ms | 3796kb | C++20 | 4.9kb | 2024-10-23 11:08:50 | 2024-10-23 11:09:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Constants
const int MOD = 998244353;
const int MAX_M = 8; // Maximum number of columns
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> grid(n);
for(auto &s : grid) cin >> s;
// Mapping characters to numerical values
// 'C' = 0, 'I' = 1, 'P' = 2
unordered_map<char, int> char_map = { {'C', 0}, {'I', 1}, {'P', 2} };
vector<char> reverse_map = {'C', 'I', 'P'};
int base = 3; // Base-3 for 'C', 'I', 'P'
// Precompute powers of the base to avoid repeated calculations
// power3[j] = 3^j
vector<ll> power3(m, 1);
for(int j = 1; j < m; ++j){
power3[j] = power3[j-1] * base;
}
// Precompute all possible states for each row based on pre-filled cells
// Each state is encoded as an integer in base-3
vector<vector<int>> allowed_states(n);
int total_states = pow(base, m);
for(int r = 0; r < n; ++r){
for(int s = 0; s < total_states; s++){
bool valid = true;
int tmp = s;
for(int j = 0; j < m; ++j){
int val = tmp % base;
tmp /= base;
if(grid[r][j] != '?'){
if(char_map[grid[r][j]] != val){
valid = false;
break;
}
}
}
if(valid){
allowed_states[r].push_back(s);
}
}
}
// Precompute transitions between consecutive rows
// transitions[r][prev_state] = list of valid curr_states
vector<vector<vector<int>>> transitions(n, vector<vector<int>>(total_states, vector<int>()));
for(int r = 1; r < n; ++r){
for(auto prev_state : allowed_states[r-1]){
for(auto curr_state : allowed_states[r]){
bool forbidden = false;
// Check all possible 2x2 subgrids between prev_state and curr_state
for(int j = 0; j < m-1 && !forbidden; j++){
// Extract the four cells of the 2x2 subgrid using precomputed powers
int prev_left = (prev_state / (ll)power3[j]) % base;
int prev_right = (prev_state / (ll)power3[j+1]) % base;
int curr_left = (curr_state / (ll)power3[j]) % base;
int curr_right = (curr_state / (ll)power3[j+1]) % base;
// Check for forbidden pattern:
// IC
// PC
if(prev_left == 1 && prev_right == 0 && curr_left == 2 && curr_right == 0){
forbidden = true;
break;
}
}
if(!forbidden){
transitions[r][prev_state].push_back(curr_state);
}
}
}
}
// Initialize DP
// dp_prev[s] = number of ways to reach state s in the previous row without forming forbidden patterns
vector<ll> dp_prev(total_states, 0);
for(auto state : allowed_states[0]){
dp_prev[state] = 1;
}
// Iterate through each row and update DP
for(int r = 1; r < n; ++r){
vector<ll> dp_curr(total_states, 0);
for(auto prev_state : allowed_states[r-1]){
if(dp_prev[prev_state] == 0) continue;
for(auto curr_state : transitions[r][prev_state]){
dp_curr[curr_state] = (dp_curr[curr_state] + dp_prev[prev_state]) % MOD;
}
}
dp_prev = move(dp_curr); // Efficiently transfer data
}
// Calculate A: Number of assignments without any forbidden pattern
ll A = 0;
for(auto state : allowed_states[n-1]){
A = (A + dp_prev[state]) % MOD;
}
// Calculate T = 3^k mod MOD, where k is the number of '?'
int k = 0;
for(int r = 0; r < n; ++r){
for(int j = 0; j < m; ++j){
if(grid[r][j] == '?') k++;
}
}
// Precompute 3^k using the power3 array if possible, else compute separately
// Since k can be up to 64 (8x8), we need to compute it efficiently
// We'll compute it using the precomputed power3 where applicable
// However, since power3 is up to m-1, and k can be larger, we compute it separately
// using binary exponentiation
auto powmod_func = [&](ll base_val, ll exp, ll mod_val) -> ll {
ll res = 1;
base_val %= mod_val;
while(exp > 0){
if(exp & 1LL){
res = res * base_val % mod_val;
}
base_val = base_val * base_val % mod_val;
exp >>=1LL;
}
return res;
};
ll T = powmod_func(3, k, MOD);
// The desired answer is (T - A) mod MOD
ll answer = (T - A + MOD) % MOD;
cout << answer;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3760kb
input:
3 3 ??? ?I? ???
output:
243
result:
ok single line: '243'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
2 2 IC PC
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Time Limit Exceeded
input:
8 8 ???????? ???????? ???????? ???????? ???????? ???????? ???????? ????????