高斯消元模板

用于求多元一次方程组的解。

实数

double A[N][N]; // 方程 0 ~ n - 1, 第 n 项为常数项
void Gauss()
{
    for (int k = 0; k < n; ++k)
    {
        int t = k;
        for (int i = k + 1; i < n; ++i)
            if (fabs(A[i][k]) > fabs(A[t][k])) t = i;
        if (fabs(A[t][k]) < eps) continue; // No Only-one Solution
        swap(A[t], A[k]);
        for (int i = 0; i < n; ++i)
        {
            if (i == k) continue;
            double t = A[i][k] / A[k][k];
            for (int j = k + 1; j <= n; ++j)
                A[i][j] -= A[k][j] * t;
        }
    }
    for (int i = 0; i < n; ++i) A[i][n] /= A[i][i];
    // ans[i] = A[i][n]
}

取模意义下

int A[N][N]; // 方程 0 ~ n - 1, 第 n 项为常数项
void Gauss ()
{
    for (int k = 0; k < n; ++k)
    {
        int t = -1;
        for (int i = k; i < n && !~t; ++i)
            if (A[i][k]) t = i;
        if (!~t) continue; // No Only-one Solution
        swap(A[t], A[k]);
        for (int i = 0; i < n; ++i) if (i ^ k)
            for (int j = k + 1,t = (LL)A[i][k] * binpow(A[k][k], mod - 2) % mod; j <= n; ++j)
                (A[i][j] -= (LL)A[k][j] * t % mod) %= mod;
    }
    for (int i = 0; i < n; ++i)
        A[i][n] = (LL)A[i][n] * binpow(A[i][i], mod - 2) % mod;
    // ans[i] = A[i][n]
}

异或

bitset<N> A[N]; // 方程 1 ~ n，第 0 项为常数项
void Gauss()
{
    for (int k = 1; k <= n; ++k)
    {
        int t = k;
        while (t <= n && !A[t][k]) ++t;
        if (t > n) continue; // No Only-one Solution
        swap(A[t], A[k]);
        for (int i = 1; i <= n; ++i)
            i ^ k && A[i][k] && (A[i] ^= A[k], 0);
    }
}