矩阵行列式的性质；

  1. 非方阵没有行列式。

  2. 原矩阵转置的行列式与原矩阵行列式相同。

  3. 原矩阵某一行（列）加上另一行（列）乘上某一系数 kk 得到的矩阵的行列式与原矩阵行列式相等。

  4. 原矩阵交换两行（列）得到的矩阵的行列式与原矩阵行列式互为相反数。

  5. 原矩阵某一行（列）乘上系数 kk 得到的矩阵的行列式是原矩阵行列式的 kk 倍。

矩阵行列式有两种求法：适用于质数模数的求法、适用于任意模数的求法。

注意事项:

  1. 建议先封装上几种行的操作函数（swaprow、redrow……），如果需要优化常数，还可以传入参数 bottomj ，变量 j 从的取值从 bottomj 到 n（如果不传则从 1 开始）。

质数模数的求法

含 bottomj 优化的写法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int n;
int a[MAXn + 10][MAXn + 10];
bool neg; int mul;
inline void swaprow(int x, int y, int bottomj) {
    for (int j = bottomj; j <= n; ++j) {
        swap(a[x][j], a[y][j]);
    }
    neg ^= 1;
}
inline void mulrow(int x, int v, int bottomj) {
    for (int j = bottomj; j <= n; ++j) {
        a[x][j] = a[x][j] * v % mod;
    }
    mul = mul * v % mod;
}
inline void redrow(int x, int y, int bottomj) { // x -= y
    for (int j = bottomj; j <= n; ++j) {
        a[x][j] = redmod(a[x][j] - a[y][j]);
    }
}
int det() {
    neg = 0; mul = 1;
    for (int rc = 1; rc <= n; ++rc) {
        int choser = -1;
        for (int i = rc; i <= n; ++i) {
            if (a[i][rc]) {
                choser = i;
                break;
            }
        }
        if (choser == -1) return 0;
        if (choser != rc) swaprow(rc, choser, rc);
        for (int i = rc + 1; i <= n; ++i) {
            if (a[i][rc]) {
                mulrow(i, a[rc][rc] * inv(a[i][rc]) % mod, rc);
                redrow(i, rc, rc);
            }
        }
    }
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        ans = ans * a[i][i] % mod;
    }
    if (neg) ans = redmod(-ans);
    ans = ans * inv(mul) % mod;
    return ans;
}

任意模数的求法

含 bottomj 优化的写法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int n;
int a[MAXn + 10][MAXn + 10];
bool neg;
inline void swaprow(int x, int y, int bottomj) {
    for (int j = bottomj; j <= n; ++j) {
        swap(a[x][j], a[y][j]);
    }
    neg ^= 1;
}
inline void redrow(int x, int y, int v, int bottomj) { // x -= y * v
    for (int j = bottomj; j <= n; ++j) {
        a[x][j] = redmod(a[x][j] - a[y][j] * v % mod);
    }
}
int det() {
    neg = 0;
    for (int rc = 1; rc <= n; ++rc) {
        int choser = -1;
        for (int i = rc; i <= n; ++i) {
            if (a[i][rc]) {
                choser = i;
                break;
            }
        }
        if (choser == -1) return 0;
        if (choser != rc) swaprow(rc, choser, rc);
        for (int i = rc + 1; i <= n; ++i) {
            if (a[i][rc]) {
                if (a[i][rc] > a[rc][rc]) swaprow(rc, i, rc);
                while (a[i][rc]) {
                    redrow(rc, i, a[rc][rc] / a[i][rc], rc);
                    swaprow(rc, i, rc);
                }
            }
        }
    }
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        ans = ans * a[i][i] % mod;
    }
    if (neg) ans = redmod(-ans);
    return ans;
}

题目

Luogu P7112 【模板】行列式求值

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 6e2;

template <typename T>
inline void read(T &a) {
    char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
    read(a), read(argv...);
}

int mod;
inline int redmod(int x) {
    return (x < 0) ? x + mod : x;
}

inline int power(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans;
}
inline int inv(int x) {
    return power(x, mod - 2);
}

int n;
int a[MAXn + 10][MAXn + 10];
bool neg;
inline void swaprow(int x, int y, int bottomj) {
    for (int j = bottomj; j <= n; ++j) {
        swap(a[x][j], a[y][j]);
    }
    neg ^= 1;
}
inline void redrow(int x, int y, int v, int bottomj) { // x -= y * v
    for (int j = bottomj; j <= n; ++j) {
        a[x][j] = redmod(a[x][j] - a[y][j] * v % mod);
    }
}
int det() {
    neg = 0;
    for (int rc = 1; rc <= n; ++rc) {
        int choser = -1;
        for (int i = rc; i <= n; ++i) {
            if (a[i][rc]) {
                choser = i;
                break;
            }
        }
        if (choser == -1) return 0;
        if (choser != rc) swaprow(rc, choser, rc);
        for (int i = rc + 1; i <= n; ++i) {
            if (a[i][rc]) {
                if (a[i][rc] > a[rc][rc]) swaprow(rc, i, rc);
                while (a[i][rc]) {
                    redrow(rc, i, a[rc][rc] / a[i][rc], rc);
                    swaprow(rc, i, rc);
                }
            }
        }
    }
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        ans = ans * a[i][i] % mod;
    }
    if (neg) ans = redmod(-ans);
    return ans;
}

signed main() {
    read(n, mod);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            read(a[i][j]);
            a[i][j] %= mod;
        }
    }
    printf("%lld\n", det());
    return 0;
}