05-算法模板/06-高斯消元

用于解线性方程组。[math]\displaystyle{ a[i][j] }[/math] 表示第 [math]\displaystyle{ i }[/math] 个方程中第 [math]\displaystyle{ j }[/math] 个未知数的系数，[math]\displaystyle{ a[i][n+1] }[/math] 是右边的常数。

模板

const double eps = 1e-12;
double a[105][105]; // a[i][0] 记录第 i 个方程的主元

// 无解：返回 -1
// 多解：返回 0
// 有唯一解：返回 1
int gauss(int x)
{
    int line = 1;
    for (int i = 1; i <= x; i++)
    {
        // 找到下面主元系数最大的方程
        int row = line;
        for (int j = line + 1; j <= x; j++)
            if (fabs(a[row][i]) < fabs(a[j][i]))
                row = j;
        if (row != line)
            std::swap(a[row], a[line]);
        // 系数为 0 则跳过
        double div1 = a[line][i];
        if (fabs(div1) < eps)
            continue;
        a[line][0] = i;
        // 调整当前方程，使主元系数变为 1
        for (int j = 1; j <= x + 1; j++)
            a[line][j] /= div1;
        // 消去下面方程中的该未知数
        for (int j = line + 1; j <= x; j++)
        {
            double div2 = a[j][i];
            for (int k = 1; k <= x + 1; ++k)
                a[j][k] -= a[line][k] * div2;
        }
        line++;
    }
    // 判无解和多解
    if (line <= x)
    {
        for (int i = line; i <= x; i++)
            if (fabs(a[i][x + 1]) > eps)
                return -1; // 无解
        return 0; // 多解
    }
    // 回代求唯一解
    for (int i = x; i >= 1; i--)
    {
        for (int j = i - 1; j >= 1; j--)
        {
            a[j][x + 1] -= a[j][i] * a[i][x + 1];
            a[j][i] = 0;
        }
    }
    return 1;
}

使用说明

- 读入 [math]\displaystyle{ n }[/math] 个方程，[math]\displaystyle{ n }[/math] 个未知数 - [math]\displaystyle{ a[i][j] }[/math]（[math]\displaystyle{ 1\le j\le n }[/math]）为第 [math]\displaystyle{ i }[/math] 个方程第 [math]\displaystyle{ j }[/math] 个未知数的系数 - [math]\displaystyle{ a[i][n+1] }[/math] 为第 [math]\displaystyle{ i }[/math] 个方程等号右边的常数 - gauss(n) 返回解的情况 - 如果有唯一解，解存储在 [math]\displaystyle{ a[i][n+1] }[/math] 中

异或方程组（bitset 优化）

对于模 [math]\displaystyle{ 2 }[/math] 意义下的方程组，可以用 bitset 优化：

bitset<1005> a[2005]; // n 个未知数，m 个方程

int gauss(int n, int m)
{
    int line = 1;
    for (int i = 1; i <= n; i++)
    {
        int row = 0;
        for (int j = line; j <= m; j++)
            if (a[j][i])
            {
                row = j;
                break;
            }
        if (!row)
            continue;
        swap(a[row], a[line]);
        for (int j = 1; j <= m; j++)
            if (j != line && a[j][i])
                a[j] ^= a[line];
        line++;
    }
    for (int i = line; i <= m; i++)
        if (a[i][n + 1])
            return -1; // 无解
    if (line <= n)
        return 0; // 多解
    return 1; // 唯一解
}