定义与形式
给定一个大小为 \(n\times n\) 的矩阵 \(A\)，则行列式
\[\det(A)=|A|=\sum_{p} (-1)^{\pi(p)} \prod A_{i,p_i}
\]
其中的 \(p\) 是一个 \(1\sim n\) 的排列，\(\pi(p)\) 为排列 \(p\) 的逆序对数。
一些性质
对于矩阵 \(A\) 来说：
-
以主对角线为对称轴翻转之后的行列式和 \(A\) 的行列式相同。
更加形象的说，就是把所有下标的两维坐标翻转一下，从 \((i,j)\) 变为 \((j,i)\)。
根据这条性质，在之后的描述中我们认为，矩阵 \(A\) 中行具有的性质列也具有（有时候省略的列的读者可自行推导）。
-
矩阵的行或列具有线性性
- 乘法情况：即 \(A\) 的某一行或某一列乘上 \(v\) 之后的行列式等于 \(v\times \det(A)\)。
- 加法情况：即 \(A\) 可以拆成两个矩阵的乘积：两个矩阵的第 \(i\) 行加和等于 \(A\) 的第 \(i\) 行，两矩阵的其他行和 \(A\) 相同。
-
交换其任意两行或者任意两列之后，行列式的值乘上了 \(-1\)。
证明：交换列会使得逆序对数的奇偶改变。再由性质 \(1\)，交换行和交换列等价。
-
有相同两行或两列的矩阵行列式为 \(0\)。
证明：\(\det(A)=-\det(A)=0\)。
-
把 \(A\) 的第 \(i\) 行乘以 \(v\) 的结果，加到第 \(j\) 行上，行列式结果不变（\(i\not= j\) ）。
根据行的线性性，我们可以把结果拆成两个矩阵结果的加和：
- 原矩阵 \(A\)
- 第 \(j\) 行等于原来的第 \(i\) 行乘 \(v\)，其他行不变的矩阵 \(A'\)。
其中第 \(2\) 个矩阵根据线性性可以把第 \(j\) 行中的 \(v\) 提取出来。这时根据性质 \(4\) 可得 \(\det(A')=0\)。
-
上三角矩阵的行列式即为对角线元素乘积。
证明：考虑如果 \(p\) 不是一个形如 \(1,2,3,\dots,n\) 的排列，那么必定存在一个位置满足 \(p_i<i\)，而这会使得贡献为 \(0\)。
求解方法
有了第 \(5,6\) 条的性质，我们就可以直接使用高斯消元把 \(A\) 消成上三角矩阵然后直接计算了。
代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); ++i)
#define FR(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
typedef long long ll;
constexpr int N = 610;
int mod;
namespace Linear{
int det(int n, int a[][N]){
int ret = 1;
FL(i, 1, n){
FL(j, i + 1, n){
while(a[i][i]){
ll t = a[j][i] / a[i][i];
FL(k, i, n) a[j][k] = (a[j][k] + mod - t * a[i][k] % mod) % mod;
swap(a[i], a[j]), ret = -ret;
}
swap(a[i], a[j]), ret = -ret;
}
}
FL(i, 1, n) ret = (ll)ret * a[i][i] % mod;
return (ret % mod + mod) % mod;
}
}
int n, a[N][N];
int main(){
scanf("%d%d", &n, &mod);
FL(i, 1, n) FL(j, 1, n) scanf("%d", &a[i][j]);
printf("%d\n", Linear::det(n, a));
return 0;
}