算法競賽經典：POJ 1830 開關問題 —— 高斯消元解異或線性方程組

問題描述

給定 n (0 < n < 29) 個開關的初始狀態與目標狀態（0/1），以及開關間的單向關聯關係（輸入 a b 表示操作 a 會翻轉 b）。求有多少種操作序列能達到目標狀態；無解輸出 Oh,it's impossible~!!。

核心建模：GF(2) 線性方程組

• 變量 x_i ∈ {0,1} 表示開關 i 是否操作（1=操作，0=不操作）。
• 每個開關最終狀態 = 初始狀態 ⊕ (所有影響它的操作之和) = 目標狀態。
• 移項得：影響矩陣 * x = 初始狀態 ⊕ 目標狀態（增廣矩陣最後一列）。
• 因操作兩次等於無操作，且順序無關，完美對應 異或 (XOR) 操作，即模 2 域 (GF(2)) 線性方程組。

關鍵細節處理

1. 單向關聯：輸入 a b 僅設置 mat[b-1][a-1] = 1（列向量視角：操作 a 影響 b）。
2. 自關聯：每個開關操作必定影響自己，mat[i][i] = 1。
3. 自由變元計數：高斯消元後，若系統有解，解的個數 = 2^free_vars。
4. 無解判定：消元後存在 0 ... 0 | 1 行（係數全 0，常數項 1）。

高斯消元核心代碼 (GF(2) 版)

const int MAXN = 35;
int a[MAXN][MAXN]; // 增廣矩陣 [equ][var+1]
int equ, var;      // 方程數、變量數

// 返回 -1:無解, 0:唯一解, >0:自由變元數
int Gauss() {
    int row = 0, col = 0, free_var = 0;
    for (; row < equ && col < var; ++row, ++col) {
        // 1. 選主元（GF(2) 下非零即可，這裡找第一個 1）
        int mx = row;
        for (int i = row + 1; i < equ; ++i)
            if (a[i][col]) { mx = i; break; }
        
        if (!a[mx][col]) { // 本列全 0，自由變元++
            --row; 
            ++free_var; 
            continue; 
        }
        
        // 2. 換行
        if (mx != row)
            for (int j = col; j <= var; ++j) swap(a[row][j], a[mx][j]);
        
        // 3. 消去下方行
        for (int i = row + 1; i < equ; ++i)
            if (a[i][col])
                for (int j = col; j <= var; ++j)
                    a[i][j] ^= a[row][j]; // XOR 消元
    }
    
    // 4. 檢查無解
    for (int i = row; i < equ; ++i)
        if (a[i][var]) return -1; // 0 = 1 矛盾
    
    return free_var; // 解的個數 = 2^free_var
}

完整程序結構

#include 
using namespace std;

int a[35][35], equ, var;

int Gauss() { /* 上述實現 */ }

void init() {
    memset(a, 0, sizeof(a));
    int n; scanf("%d", &n);
    equ = var = n;
    for (int i = 0; i < n; ++i) scanf("%d", &a[i][n]);     // 初始狀態
    for (int i = 0; i < n; ++i) { int x; scanf("%d", &x); a[i][n] ^= x; } // 目標狀態 XOR
    for (int i = 0; i < n; ++i) a[i][i] = 1;               // 自關聯
    int l, r;
    while (scanf("%d %d", &l, &r) == 2 && l + r)           // 關聯關係
        a[r-1][l-1] = 1;                                   // 單向：l 影響 r
}

int main() {
    int T; scanf("%d", &T);
    for (int kase = 1; T--; ++kase) {
        init();
        int free_var = Gauss();
        if (free_var == -1) puts("Oh,it's impossible~!!");
        else printf("%d\n", 1 << free_var); // 2^free_var
    }
    return 0;
}

複雜度分析

• 時間：O(n^3)，n ≤ 30 極快。
• 空間：O(n^2)。

避坑指南

1. 務必處理自關聯：a[i][i]=1，否則 WA。
2. 單向邊方向：輸入 a b → 矩陣 [b-1][a-1]=1（列消元視角）。
3. 增廣列計算：a[i][n] = init[i] ^ target[i]。
4. 自由變元計數：主元選擇失敗時 free_var++ 且 row-- 保持行不變。
5. 多組測試數據：每組 memset 清零。