QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#668079#5576. Advertising ICPCenze114514TL 1ms3796kbC++204.9kb2024-10-23 11:08:502024-10-23 11:09:02

Judging History

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

  • [2024-10-23 11:09:02]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3796kb
  • [2024-10-23 11:08:50]
  • 提交

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
????????
????????
????????
????????
????????
????????
????????
????????

output:


result: