POJ 1830 開關問題：異或方程組高斯消元法

題目大意

N ≤ 28 個開關，初始狀態與目標狀態給定。操作開關 i 會翻轉自身及關聯開關 j 的狀態。每個開關最多操作一次。求達到目標狀態的方案數。

數學建模：GF(2) 線性方程組

• 變量 x_i ∈ {0,1} 表示開關 i 是否操作。
• 第 k 個開關最終狀態變化：初始[k] ⊕ (Σ x_i * A[i][k]) = 目標[k]，其中 A[i][k]=1 若操作 i 影響 k。
• 整理得 A * x = b (mod 2)，b[k] = 初始[k] ⊕ 目標[k]。

異或高斯消元

標準高斯消元，把減法換為異或（^）。步驟：

1. 列主元：找當前行以下有 1 的行交換上來。
2. 消元：對下方行，若該列為 1，則整行異或主元行。
3. 判斷：若出現 0 = 1 行 → 無解。
4. 自由變量個數 f → 解的個數 = 2^f。

C++ 代碼

#include 
using namespace std;
const int MAXN = 30;
int mat[MAXN][MAXN], rhs[MAXN]; // 增廣矩陣

int gauss(int n) {
    int row = 0, col = 0, freeVar = 0;
    while (row < n && col < n) {
        int sel = row;
        while (sel < n && !mat[sel][col]) ++sel;
        if (sel == n) { ++freeVar; ++col; continue; }
        if (sel != row) {
            for (int j = col; j < n; ++j) swap(mat[row][j], mat[sel][j]);
            swap(rhs[row], rhs[sel]);
        }
        for (int i = row + 1; i < n; ++i) {
            if (mat[i][col]) {
                for (int j = col; j < n; ++j) mat[i][j] ^= mat[row][j];
                rhs[i] ^= rhs[row];
            }
        }
        ++row; ++col;
    }
    // 檢查無解
    for (int i = row; i < n; ++i) if (rhs[i]) return -1;
    return freeVar;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        memset(mat, 0, sizeof(mat));
        for (int i = 0; i < n; ++i) { cin >> rhs[i]; mat[i][i] = 1; }
        for (int i = 0; i < n; ++i) {
            int t; cin >> t; rhs[i] ^= t;
        }
        int u, v;
        while (cin >> u >> v, u || v) {
            // 注意：題目給的是 "操作 i 影響 j"，矩陣行是方程(受影響者)，列是變量(操作者)
            // 方程 j: x_j ⊕ Σ x_i = b_j  → mat[j][i] = 1
            mat[v-1][u-1] = 1;
        }
        int f = gauss(n);
        if (f == -1) cout << "Oh,it's impossible~!!\n";
        else cout << (1 << f) << '\n';
    }
    return 0;
}

關鍵細節

• 矩陣構建：方程對應「被影響開關」，變量對應「操作開關」。題目給 i j 表示操作 i 影響 j，故 mat[j-1][i-1] = 1。
• 對角線初始化 mat[i][i]=1：操作自身翻轉自身。
• 自由變量計數：消元後非主元列即自由變量。
• 1 << f 計算方案數，f ≤ 28 可用 int 或 long long。

總結

POJ 1830 是「GF(2) 線性方程組高斯消元」的標準題。核心模板：增廣矩陣構建 → 異或消元 → 自由變量計數 → 2^f。同模板解決 HDU 1222、Codeforces 異或方程組計數問題。