学《高等代数》第二章的时候过来搜了搜模板，结果真搜到了。于是水一篇题解。
本文部分内容来自《高等代数》。
行列式定义
对于一个 \(n\) 阶行列式
\[A_{n \times n}=
\begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix}\]
其结果为所有不同行不同列的元素乘积的代数和。用数学语言写为：
\[\sum_{j_1j_2 \cdots j_n} (-1) ^ {\tau(j_1j_2\cdots j_n)} a_{1j_1}a_{2j_2}\cdots a_{nj_n}
\]
其中 \(j_1j_2 \cdots j_n\) 为 \(1 \sim n\) 的一个排列。\(\tau(j_1j_2 \cdots j_n)\) 表示排列 \(j\) 的逆序数的个数。
可以看出，如果 \(\tau(j_1 \sim j_n)\) 为偶数，那么该排列对答案的贡献为正。否则为负。
行列式性质
《高代》里原本有七条性质，这里只证明有用的五条。
\[\begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix} =
\begin{vmatrix}
a_{11}& a_{21}& \cdots & a_{n1} \\
a_{12}& a_{22}& \cdots & a_{n2} \\
\vdots & \vdots & \ddots & \vdots \\
a_{1n}& a_{2n}& \cdots & a_{nn}
\end{vmatrix} \]
\[\begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
ka_{i1} & ka_{i2} & \cdots & ka_{in} & \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix} =
k
\begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
a_{i1} & a_{i2} & \cdots & a_{in} & \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix}
\]
证明：
首先考虑 \(n\) 级行列式的 \(n!\) 项。如果把他们分成 \(n\) 组，一定有一种方案，使得第 \(1\) 组中都含有 \(a_{i1}\)，第 \(2\) 组中都含有 \(a_{i2}\)，以此类推。如果第 \(j\) 项提出 \(a_{ij}\) 后记作 \(A_{ij}\)，那么有
\[\begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix} =
a_{i1}A_{i1} + a_{i2}A_{i2} + \cdots + a_{in}A_{in} \\
= \sum_{j = 1}^{n} a_{ij}A_{ij}
\]
这将方便我们后面的讨论。
现在证明性质二：
\[\begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
ka_{i1} & ka_{i2} & \cdots & ka_{in} & \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix} =
ka_{i1}A_{i1} + ka_{i2}A_{i2} + \cdots + ka_{in}A_{in} \\
= k(a_{i1}A_{i1} + a_{i2}A_{i2} + \cdots + a_{in}A_{in})
= k
\begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
a_{i1} & a_{i2} & \cdots & a_{in} \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix}
\]
\[\begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
b_1 + c_1 & b_2 + c_2 & \cdots & b_n + c_n \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix} \\
=
\begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
b_1 & b_2 & \cdots & b_n \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix} +
\begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
c_1 & c_2 & \cdots & c_n \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix}
\]
证明：
原行列式可写成 \((b_1 + c_1)A_{i1} + (b_2 + c_2)A_{i2} + \cdots + (b_n + c_n)A_{in}\)，这等于右式。
- 性质四：把第 \(k\) 行的倍数加到第 \(i\) 行，行列式不变。
证明太容易而公式又太难打，就不写了。
证明：
\[\begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
a_{i1} & a_{i2} & \cdots & a_{in} \\
\vdots & \vdots & &\vdots \\
a_{k1} & a_{k2} & \cdots &a_{kn} \\
\vdots & \vdots & &\vdots \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix} = \begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
a_{i1} + a_{k1}& a_{i2} + a_{k2}& \cdots & a_{in} + a_{kn}\\
\vdots & \vdots & &\vdots \\
a_{k1} & a_{k2} & \cdots &a_{kn} \\
\vdots & \vdots & &\vdots \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix} \\
= \begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
a_{i1} + a_{k1}& a_{i2} + a_{k2}& \cdots & a_{in} + a_{kn}\\
\vdots & \vdots & &\vdots \\
-a_{i1} & -a_{i2} & \cdots & -a_{in} \\
\vdots & \vdots & &\vdots \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix} \\
= \begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
a_{k1} & a_{k2} & \cdots & a_{kn}\\
\vdots & \vdots & &\vdots \\
-a_{i1} & -a_{i2} & \cdots & -a_{in} \\
\vdots & \vdots & &\vdots \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix} \\
= - \begin{vmatrix}
a_{11}& a_{12}& \cdots & a_{1n} \\
a_{21}& a_{22}& \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
a_{k1} & a_{k2} & \cdots & a_{kn}\\
\vdots & \vdots & &\vdots \\
a_{i1} & a_{i2} & \cdots & a_{in} \\
\vdots & \vdots & &\vdots \\
a_{n1}& a_{n2}& \cdots & a_{nn}
\end{vmatrix}
\]
其中第一步是利用性质四，将第 \(k\) 行加到了第 \(i\) 行上。
第二步是利用性质四，将第 \(i\) 行减去第 \(k\) 行。
第三步是利用性质四，将第 \(i\) 行加到了第 \(k\) 行上。
最后一步是利用性质二，将第 \(i\) 行提出 \(-1\)。
证毕。
特殊的行列式
- 对角行列式
形如
\(\begin{vmatrix}
a_{11} & 0 & \cdots & 0 \\
0 & a_{22} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & a_{nn}
\end{vmatrix}\)
的行列式称为对角行列式。其结果为 \(a_{11} \times a_{22} \cdots a_{nn}\)
- 三角行列式
形如 \(\begin{vmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
0 & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & & \vdots \\
0 & 0 & 0 & a_{nn} \\
\end{vmatrix}\) 的行列式被称为三角行列式，其结果与对角行列式相同。
行列式计算
显然，如果按照定义，我们需要 \(O(n \times n!)\) 的复杂度。显然无法接受。
由于存在一些特殊的行列式，可以考虑将原行列式转化为三角行列式后求值。思路就是将原行列式利用性质一到四进行转化。
例如有行列式 \(\begin{vmatrix}
2 & 3 & 5 \\
3 & 4 & 7 \\
4 & 3 & 2
\end{vmatrix}\)，首先可以将 \(2 \sim 3\) 行分别加上第一行的 \(-\dfrac{3}{2}, -2\) 倍，化为 \(\begin{vmatrix}
2 & 3 & 5 \\
0 & -\dfrac{1}{2} & -\dfrac{1}{2} \\
0 & -3 & -8
\end{vmatrix}\)。
接下来，把第三行加上第二行的 \(-6\) 倍，可得 \(\begin{vmatrix}
2 & 3 & 5 \\
0 & -\dfrac{1}{2} & -\dfrac{1}{2} \\
0 & 0 & -5
\end{vmatrix}\)
于是原式化为了一个三角行列式。对角线乘积即为答案 \(5\)。
这个方法类似高斯消元的过程。因此就把它叫做高斯消元吧。
可以看出，这个方法的时间复杂度是 \(O(n ^ 3)\) 的，完全可以接受。
带模数行列式计算
如果带模数怎么算行列式的值呢？
有一种方法叫做辗转相减法，可以完美的解决这个问题。
比如有行列式 \(\begin{vmatrix}
3 & 2\\
4 & 1
\end{vmatrix}\)，首先先用第二行的第一个数除以第一行第一个数，得到 \(1\)。（这里是下取整）。
然后用第二行减去第一行 \(\times 1\)，得到 \(\begin{vmatrix}
3 & 2\\
1 & -1
\end{vmatrix}\)
容易证明第二行第一个数在操作完之后一定小于第一行第一个数。因此交换 \(1, 2\) 行，得到 \(-\begin{vmatrix}
1 & -1\\
3 & 2
\end{vmatrix}\)。
重复上述操作，直到第一行为 \(0\)。得到这样的行列式：\(\begin{vmatrix}
0 & 5\\
1 & -1
\end{vmatrix}\)。
最后再把一、二行交换即可得到下三角行列式：
\[-\begin{vmatrix}
1 & -1\\
0 & 5
\end{vmatrix}\]
答案即为 \(-5\)。
由于在辗转相减的过程中可以取模，所以这个问题就被完美解决了。
分析一下复杂度。易证辗转相减的复杂度与欧几里得算法类似，为 \(O(\log n)\) 级别。如果记交换两行复杂度为 \(O(n)\)，那么总复杂度就为 \(O(n ^ 2(\log n + n))\)。
注意：两行交换时千万别忘变号！！！
代码
#include <algorithm>
#include <cstdio>
#define int long long
using namespace std;
const int N = 610;
int n, p, w[N][N], f;
void Swap(int &a, int &b) {
for (int i = 1; i <= n; i ++ )
swap(w[a][i], w[b][i]);
f ^= 1; // 变号
}
int gauss() {
for (int i = 1; i <= n; i ++ )
for (int j = i + 1; j <= n; j ++ ) {
while (w[i][i]) {
int K = (int)w[j][i] / w[i][i];
for (int k = i; k <= n; k ++ )
((w[j][k] -= K * w[i][k] % p) += p) %= p;
Swap(i, j);
} Swap(i, j);
}
int ans = 1;
for (int i = 1; i <= n; i ++ )
(ans *= w[i][i]) %= p;
return (f ? (-ans + p) % p : (ans + p) % p);
}
signed main() {
scanf("%lld%lld", &n, &p);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
scanf("%lld", &w[i][j]);
return 0 & printf("%lld\n", gauss());;
}
本文公式很多，可能有笔误。希望大家可以指出。