POJ 1830 開關問題：高斯消元法求解 GF(2) 線性方程組

POJ 1830 開關問題：高斯消元法求解 GF(2) 線性方程組

N 個開關，操作某開關會翻轉其關聯開關狀態。給定初始狀態與目標狀態，求達到目標的操作方案數 (不計順序)，每開關最多操作一次。本質是模 2 線性方程組求解，自由度即為方案數的 2 次冪。

數學建模

• 變量 x_i ∈ {0,1} 表示第 i 個開關是否操作。
• 方程：初始狀態 ⊕ (影響矩陣 × x) = 目標狀態 → 影響矩陣 × x = 初始 ⊕ 目標 (模 2)。
• 增廣矩陣 a[i][j]：前 N 列為係數，第 N+1 列為常數項。
• 對角線初始化為 1 (操作自身翻轉)，讀入關聯關係置對應位為 1。

高斯消元 (模 2)

1. 列主元消元：尋找當前列下方非零行交換上來。
2. 消去下方行：若下方行該列為 1，則該行異或 (XOR) 當前行。
3. 消元後檢查：若存在全零行但常數項為 1 → 無解。
4. 自由變量個數 = N - rank，方案數 = 2^自由度。

C++ 實現

#include <iostream>
#include <cstring>
using namespace std;

int a[32][32], n;

int gauss() {
    int i = 0, j = 0, k, r, u;
    while (i < n && j < n) {
        r = i;
        for (k = i; k < n; k++) if (a[k][j]) { r = k; break; }
        if (a[r][j]) {
            if (r != i) for (k = 0; k <= n; k++) swap(a[r][k], a[i][k]);
            for (u = i+1; u < n; u++)
                if (a[u][j])
                    for (k = i; k <= n; k++) a[u][k] ^= a[i][k];
            i++;
        }
        j++;
    }
    for (u = i; u < n; u++) if (a[u][n]) return -1; // 無解
    return 1 << (n - i); // 2^(自由變量數)
}

int main() {
    int T; cin >> T;
    while (T--) {
        memset(a, 0, sizeof(a));
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i][n]; // 初始狀態
        for (int i = 0; i < n; i++) {
            int x; cin >> x;
            a[i][i] = 1;
            a[i][n] ^= x; // 常數項 = 初始 ⊕ 目標
        }
        int x, y;
        while (cin >> x >> y) {
            if (x == 0 && y == 0) break;
            a[y-1][x-1] = 1; // 操作 x 影響 y
        }
        int ans = gauss();
        if (ans == -1) cout << "Oh,it's impossible~!!" << endl;
        else cout << ans << endl;
    }
    return 0;
}

關鍵點總結

• 模 2 下加法 = 減法 = XOR，極大簡化運算。
• 矩陣大小 ≤ 30，O(N³) 完全足夠。
• 輸入關聯關係以 0 0 結束，需仔細處理多測試用例讀取。