高斯消元CSP-S

💡 核心思想

高斯消元是求解线性方程组的标准算法。通过初等行变换将增广矩阵化为上三角矩阵（消元），然后从下往上回代求解。在模 2 意义下（异或方程组），高斯消元可以解决开关问题、灯灭问题等组合问题。

🎯 直觉理解

想象你在解一个谜题，每个开关控制多个灯。高斯消元就像"逐个击破"：先处理第一个灯的开关关系，把其他方程中的第一个灯消掉；然后处理第二个灯，依此类推。最后从下往上回代，就像拼图的最后几块，一个一个放回去。

📝 算法流程

1. 写出增广矩阵（n 行 n+1 列）
2. 对于每一列 col（从左到右）：
3. 在第 col 行及以下找绝对值最大的主元行，交换到第 col 行
4. 用主元行消去下方所有行的第 col 列元素
5. 回代：从最后一行开始，逐个求解变量
6. 如果某行系数全为 0 但常数不为 0，则无解；如果全为 0，则有无穷多解

$$a_{ij} = a_{ij} - \frac{a_{ic}}{a_{cc}} \cdot a_{cj} \quad (i > c, \text{ 所有 }j)$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
const double EPS = 1e-9;

// 高斯消元求解线性方程组 Ax = b
vector gauss(vector> a) {
    int n = a.size();
    for (int col = 0, row = 0; col < n && row < n; col++, row++) {
        // 找主元
        int sel = row;
        for (int i = row; i < n; i++)
            if (abs(a[i][col]) > abs(a[sel][col])) sel = i;
        if (abs(a[sel][col]) < EPS) { row--; continue; }
        swap(a[sel], a[row]);
        
        // 消元
        for (int i = row + 1; i < n; i++) {
            double c = a[i][col] / a[row][col];
            for (int j = col; j <= n; j++) a[i][j] -= c * a[row][j];
        }
    }
    
    // 回代
    vector ans(n);
    for (int i = n - 1; i >= 0; i--) {
        double sum = 0;
        for (int j = i + 1; j < n; j++) sum += ans[j] * a[i][j];
        if (abs(a[i][i]) < EPS) continue; // 无穷多解或无解
        ans[i] = (a[i][n] - sum) / a[i][i];
    }
    return ans;
}

int main() {
    vector> a = {
        {2, 1, -1, 8},
        {-3, -1, 2, -11},
        {-2, 1, 2, -3}
    };
    auto ans = gauss(a);
    for (double x : ans) cout << x << " "; // 2 3 -1
    cout << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目