高斯消元

解线性方程组

void gauss(int tot)
{
    for (int i = 1; i <= tot; i++)
    {
        int idx = i;
        for (int j = i + 1; j <= tot; j++)
            if (fabs(mat[j][i]) > fabs(mat[idx][i]))
                idx = j;
        if (idx != i)
            for (int j = i; j <= tot + 1; j++)
                swap(mat[i][j], mat[idx][j]);
        for (int j = 1; j <= tot; j++)
            if (i != j)
            {
                double rate = mat[j][i] / mat[i][i];
                for (int k = i; k <= tot + 1; k++)
                    mat[j][k] -= rate * mat[i][k];
            }
    }
}

异或方程组

GUGUGU

矩阵求逆

// P4783.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 440, mod = 1e9 + 7;

int n, mat[MAX_N][MAX_N << 1];

int fpow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

void gauss_inverse()
{
    for (int i = 1; i <= n; i++)
    {
        int key = 0;
        for (int j = i; j <= n && key == 0; j++)
            if (mat[j][i] != 0)
                key = j;
        if (key != i)
        {
            if (key == 0)
                puts("No Solution"), exit(0);
            for (int j = i; j <= (n << 1); j++)
                swap(mat[i][j], mat[key][j]);
        }
        int inv = fpow(mat[i][i], mod - 2);
        for (int j = i; j <= (n << 1); j++)
            mat[i][j] = 1LL * mat[i][j] * inv % mod;
        for (int j = 1; j <= n; j++)
            if (i != j)
            {
                inv = mat[j][i];
                for (int k = i; k <= (n << 1); k++)
                    mat[j][k] = (0LL + mat[j][k] + mod - 1LL * inv * mat[i][k] % mod) % mod;
            }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        mat[i][n + i] = 1;
        for (int j = 1; j <= n; j++)
            scanf("%d", &mat[i][j]);
    }
    gauss_inverse();
    for (int i = 1; i <= n; i++, puts(""))
        for (int j = n + 1; j <= (n << 1); j++)
            printf("%d ", mat[i][j]);
    return 0;
}

多项式插值

具体见：https://kalorona.com/oi/fortuna-oj-pa-apr-19/

求行列式

int gauss()
{
    int res = 1;
    for (int i = 0; i < n - 1; i++)
    {
        int key = i;
        for (int j = i; j < n - 1; j++)
            if (mat[j][i] != 0)
            {
                key = j;
                break;
            }
        if (key != i)
        {
            res = mod - res;
            for (int j = i; j < n - 1; j++)
                swap(mat[i][j], mat[key][j]);
        }
        int inv = fpow(mat[i][i], mod - 2);
        for (int j = i + 1; j < n - 1; j++)
        {
            int rate = 1LL * mat[j][i] * inv % mod;
            for (int k = i; k < n - 1; k++)
                mat[j][k] = (0LL + mat[j][k] + mod - 1LL * rate * mat[i][k] % mod) % mod;
        }
    }
    for (int i = 0; i < n - 1; i++)
        res = 1LL * res * mat[i][i] % mod;
    return res;
}