模质数高斯消元求解行列式模版

高斯消元的用法总结

• 求解线性方程组
• 行列式计算
• 矩阵求逆
• 解异或方程组

参考

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
const int MOD = 10007;
int n;
int a[N][N];
int res = 1;

int qmi(int a, int k, int p)
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (long long)res * a % p;
        a = (long long)a * a % p;
        k >>= 1;
    }
    return res;
}

void gauss()
{
    int c, r;
    for (c = 1, r = 1; c < n; c++)
    {
        int t = r;
        for (int i = r; i < n; i++)
            if (abs(a[i][c]) > abs(a[t][c]))
                t = i;
        if (!a[t][c])
        {
            res = 0;
            return;
        }
        if (t != r)
        {
            res *= -1; // 交换任意两行，行列式值取反
            for (int i = c; i < n; i++)
                swap(a[t][i], a[r][i]);
        }
        res = res * a[r][c] % MOD;
        for (int i = r + 1; i < n; i++)
            if (a[i][c])
            {
                int tmp = a[i][c] * qmi(a[r][c], MOD - 2, MOD) % MOD;
                for (int j = n - 1; j >= c; j--)
                    a[i][j] = (a[i][j] - a[r][j] * tmp % MOD) % MOD;
            }
        r++;
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            int x;
            scanf("%d", &x);
            if (x)
            {
                a[i][i]++;
                a[i][j]--;
            }
        }
    gauss();
    cout << (res + MOD) % MOD;
    return 0;
}