HDU 4421 Bit Magic：位運算矩陣逆向構造 + 2-SAT 逐位求解

問題描述

給定 N × N (N ≤ 500) 矩陣 B，已知其由某數組 A[1..N] 通過位運算生成：

• i == j：B[i][j] = 0
• i, j 同奇/同偶：B[i][j] = A[i] | A[j]（或）
• i, j 一奇一偶：B[i][j] = A[i] ^ A[j]（異或）

判斷是否存在滿足條件的數組 A。

核心洞見：位獨立性 → 逐位 2-SAT

• 位運算（|, &, ^）在各二進制位上相互獨立
• B[i][j] 的第 k 位僅取決於 A[i]、A[j] 的第 k 位
• 每個 A[i] 的第 k 位只有 0/1 兩種取值 → 布爾變量
• 每個 B[i][j] 的第 k 位給出一個約束 → 2-SAT 子句
• 31 位（B[i][j] < 2³¹）分別求解，全滿足則整體有解

逐位約束建模

設變量 xᵢ = A[i] 第 k 位。對每對 (i,j)：

完整代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

struct TwoSAT {
    int n;
    vector> g;
    vector val, comp, order;
    TwoSAT(int n=0) { init(n); }
    void init(int n_) { n = n_; g.assign(2*n, {}); }
    // x = true/false 表示變量 x 取值
    void add_implication(int x, bool xv, int y, bool yv) {
        // x= xv → y= yv   等價於   (¬x∨y)  其中 x 取 xv 為真
        g[2*x + xv].push_back(2*y + yv);
        g[2*y + !yv].push_back(2*x + !xv); // 逆否命題
    }
    void add_or(int x, bool xv, int y, bool yv) {
        // (x=xv) ∨ (y=yv)
        add_implication(x, !xv, y, yv);
        add_implication(y, !yv, x, xv);
    }
    void add_xor(int x, int y) { // x != y
        add_or(x, 0, y, 0);
        add_or(x, 1, y, 1);
    }
    void add_xnor(int x, int y) { // x == y
        add_or(x, 0, y, 1);
        add_or(x, 1, y, 0);
    }

    bool solve() {
        val.assign(n, 0);
        comp.assign(2*n, -1);
        order.clear();
        vector vis(2*n, 0);
        function dfs1 = [&](int u) {
            vis[u] = 1;
            for (int v : g[u]) if (!vis[v]) dfs1(v);
            order.push_back(u);
        };
        function dfs2 = [&](int u, int c) {
            comp[u] = c;
            for (int v : g[u^1]) if (comp[v] == -1) dfs2(v, c);
        };
        for (int i = 0; i < 2*n; ++i) if (!vis[i]) dfs1(i);
        reverse(order.begin(), order.end());
        int cid = 0;
        for (int u : order) if (comp[u] == -1) dfs2(u, cid++);
        for (int i = 0; i < n; ++i) {
            if (comp[2*i] == comp[2*i+1]) return false;
            val[i] = comp[2*i] > comp[2*i+1]; // 拓撲序賦值
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    while (cin >> N) {
        vector> B(N, vector(N));
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                cin >> B[i][j];

        bool ok = true;
        for (int bit = 0; bit < 31 && ok; ++bit) {
            TwoSAT solver(N);
            int mask = 1 << bit;
            for (int i = 0; i < N; ++i) {
                for (int j = i+1; j < N; ++j) {
                    int target = (B[i][j] & mask) ? 1 : 0;
                    bool iodd = i & 1, jodd = j & 1;
                    if (iodd && jodd) { // OR
                        if (target == 0) {
                            solver.add_or(i, 0, j, 0); // x=0 ∨ y=0  → 至少一個為0
                        } else {
                            // 允許 (0,1)(1,0)(1,1) → 禁止 (0,0)
                            solver.add_or(i, 1, j, 1); // x=1 ∨ y=1
                        }
                    } else if (!iodd && !jodd) { // AND
                        if (target == 0) {
                            // 禁止 (1,1)
                            solver.add_or(i, 0, j, 0);
                        } else {
                            // 強制 (1,1) → 兩個單元子句
                            solver.add_or(i, 1, i, 1); // x=1
                            solver.add_or(j, 1, j, 1); // y=1
                        }
                    } else { // XOR
                        if (target == 0) solver.add_xnor(i, j);
                        else solver.add_xor(i, j);
                    }
                }
            }
            if (!solver.solve()) ok = false;
        }
        cout << (ok ? "YES" : "NO") << '\n';
    }
    return 0;
}

關鍵技巧總結

總結

HDU 4421 是位運算 + 2-SAT的經典結合。核心邏輯鏈：
矩陣由位運算生成 → 各位獨立 → 每位構成布爾約束系統 → 2-SAT 判斷可滿足性。
此模式廣泛適用於「位運算逆向構造」、「邏輯電路驗證」、「布爾矩陣分解」等問題。