Tối ưu hóa bài toán chuyển trạng thái với Bitmask DP và BFS

Trong các bài toán yêu cầu tìm số bước tối thiểu để chuyển đổi giữa các trạng thái, Quy hoạch động trạng thái (Bitmask DP) thường được nghĩ đến đầu tiên. Tuy nhiên, nếu trạng thái mới (nmask) có thể lớn hơn trạng thái hiện tại (mask), việc cập nhật DP theo thứ tự thông thường sẽ gặp lỗi logic do không thể dùng nmask để cập nhật ngược lại các trạng thái khác.

Để giải quyết vấn đề này, thay vì chạy DP nhiều lần, giải pháp tối ưu và an toàn hơn là sử dụng Thuật toán tìm kiếm theo chiều rộng (BFS) để đảm bảo tìm được đường đi ngắn nhất trên đồ thị trạng thái.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 2e6 + 10;
const int INF = 1e9;

int n, m;
int a[15][105];
int dist[MAXN];

void solve() {
    cin >> n >> m;
    for (int j = 1; j <= m; ++j) {
        for (int i = 0; i < n; ++i) {
            cin >> a[i][j];
        }
    }
    
    fill(dist, dist + (1 << n), INF);
    queue<int> q;
    
    int start_mask = (1 << n) - 1;
    dist[start_mask] = 0;
    q.push(start_mask);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int j = 1; j <= m; ++j) {
            int v = u;
            for (int i = 0; i < n; ++i) {
                if (a[i][j] == 1 && (u & (1 << i))) {
                    v ^= (1 << i);
                } else if (a[i][j] == -1 && !(u & (1 << i))) {
                    v ^= (1 << i);
                }
            }
            if (dist[v] > dist[u] + 1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    
    if (dist[0] == INF) cout << -1;
    else cout << dist[0];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Ứng dụng Nguyên lý Bao hàm - Loại trừ và Phân tích thừa số nguyên tố

Đối với bài toán đếm số đường đi dựa trên các ước nguyên tố, việc duyệt toàn bộ sẽ có độ phức tạp quá lớn. Hướng tiếp cận hiệu quả là phân tích các thừa số nguyên tố của từng phần tử và lưu trữ thông tin trực tiếp lên các ước này.

Khi tính toán, việc một số có nhiều ước nguyên tố chung sẽ dẫn đến tính trùng lặp. Lúc này, Nguyên lý Bao hàm - Loại trừ (Inclusion-Exclusion) kết hợp với Bitmask để duyệt các tập hợp con của ước nguyên tố là chìa khóa để giải quyết. Nếu tập hợp có số lượng ước lẻ, ta cộng dồn; nếu chẵn, ta trừ đi (tương tự tư tưởng của tổng tiền tố đa chiều).

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1e6 + 10;
const int MOD = 998244353;

int n;
int primes[MAXN], prime_cnt = 0;
bool is_composite[MAXN];
vector<int> prime_factors[MAXN];
long long factor_count[MAXN];

void sieve() {
    for (int i = 2; i < MAXN; ++i) {
        if (!is_composite[i]) primes[++prime_cnt] = i;
        for (int j = 1; j <= prime_cnt && 1LL * i * primes[j] < MAXN; ++j) {
            is_composite[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

void precompute_factors() {
    for (int i = 1; i <= prime_cnt; ++i) {
        for (int j = primes[i]; j < MAXN; j += primes[i]) {
            prime_factors[j].push_back(primes[i]);
        }
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        long long val;
        cin >> val;
        
        long long paths = (i == 1 ? 1 : 0);
        int num_factors = prime_factors[val].size();
        vector<long long> subsets;
        
        for (int mask = 1; mask < (1 << num_factors); ++mask) {
            long long prod = 1;
            int bits = 0;
            for (int j = 0; j < num_factors; ++j) {
                if (mask & (1 << j)) {
                    prod *= prime_factors[val][j];
                    bits++;
                }
            }
            
            if (bits % 2 != 0) {
                paths = (paths + factor_count[prod]) % MOD;
            } else {
                paths = (paths - factor_count[prod] + MOD) % MOD;
            }
            subsets.push_back(prod);
        }
        
        if (i == n) {
            cout << paths;
            return;
        }
        
        for (long long sub : subsets) {
            factor_count[sub] = (factor_count[sub] + paths) % MOD;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sieve();
    precompute_factors();
    solve();
    return 0;
}

Các bẫy kỹ thuật và mô hình thuật toán trong thi đấu thực tế

Lỗi kiểu dữ liệu trong bài toán mở đầu: Một sai lầm phổ biến gây mất thời gian và chịu phạt (penalty) là lưu trữ các giá trị số (như điểm số, ID, hoặc sức mạnh) dưới dạng chuỗi (string) thay vì kiểu số nguyên. Điều này dẫn đến việc so sánh sai lệch và gây ra lỗi Wrong Answer. Cần đặc biệt chú ý kiểm tra kiểu dữ liệu của các biến đầu vào ngay từ khi đọc đề.

Kết hợp Dijkstra và Bitmask DP: Đối với các bài toán yêu cầu tìm đường đi ngắn nhất kết hợp với việc chọn tập hợp đối tượng (như bài E), hướng tiếp cận chuẩn là sử dụng thuật toán Dijkstra để xử lý đồ thị, sau đó dùng Bitmask DP để quản lý trạng thái chọn. Việc nhận diện nhanh mô hình này giúp tối ưu hóa thời gian phản xạ khi đọc đề.

Xử lý bài toán nghịch đảo, tính chẵn lẻ và GCD: Trong các bài toán liên quan đến thao tác trên mảng (như bài D), kết quả thường phụ thuộc vào tính chẵn lẻ của số lần thao tác. Việc duy trì số cặp nghịch đảo (inversions) giúp xác định trạng thái thắng/thua ban đầu. Khi có các truy vấn sửa đổi, sự thay đổi tính chẵn lẻ của độ dài đoạn (len) và bước nhảy (d) có thể được xác định thông qua ước chung lớn nhất (GCD). Cụ thể, tính chẵn lẻ của thao tác chỉ thay đổi khi len / gcd(len, d) là một số lẻ.