前置知识

  • ∑\sum 为累加符号，∏\prod 为累乘符号。
  • 上三角矩阵指只有对角线及其右上方有数值其余都是 00 的矩阵。
  • 如果一个矩阵的对角线全部为 11 那么这个矩阵为单位矩阵记作 II。
  • 对于矩阵 An,mA_{n,m} 和矩阵 Bm,nB_{m,n} 满足 Ai,j=Bj,iA_{i,j}=B_{j,i} 记作 A=BTA=B^T。
  • 如果 i,j∈[1,n]i,j\in[1,n] 满足 i<ji<j 且 pi>pjp_i>p_j，那么称 (pi,pj)(p_i,p_j) 为一对逆序对。
  • 假设 pp 是一个排列，那么 τ(p)\tau(p) 为 pp 中逆序对的个数。

定义

行列式 AA 为 nn 阶方阵，那么 ∣A∣|A| 为该矩阵的行列式，记作 det⁡(A)\operatorname{det}(A)。

∣a1,1a1,2⋯a1,na2,1a2,2⋯a2,n⋯⋯⋯⋯an,1an,2⋯an,n∣=∑j1,j2,⋯ ,jn(−1)N(j1,j2,⋯ ,jn)∏i=1nai,ji\begin{vmatrix} a_{1,1} & a_{1,2} &\cdots & a_{1,n} \\ a_{2,1} & a_{2,2} &\cdots & a_{2,n} \\ \cdots & \cdots &\cdots & \cdots \\ a_{n,1} & a_{n,2} &\cdots & a_{n,n} \\ \end{vmatrix}=\sum_{j_1,j_2,\cdots ,j_n}(-1)^{N(j_1,j_2,\cdots ,j_n)}\prod_{i=1}^n a_{i,j_i}

几何意义

对于一个 nn 维的向量空间中的 nn 个向量，我们可以构造一个 nn 阶行列式。这个行列式的绝对值等于由这 nn 个向量所构成的平行体的体积。

具体来说，如果我们有 nn 个向量 v1⃗,v2⃗,...,vn⃗\vec{v_1}, \vec{v_2}, ..., \vec{v_n}，我们可以将这些向量的坐标构造成一个n阶行列式：

[v1,1v1,2⋯v1,nv2,1v2,2⋯v2,n⋯⋯⋯⋯vn,1vn,2⋯vn,n]\begin{bmatrix} v_{1,1} & v_{1,2} & \cdots & v_{1,n} \\ v_{2,1} & v_{2,2} & \cdots & v_{2,n} \\ \cdots & \cdots & \cdots & \cdots \\ v_{n,1} & v_{n,2} & \cdots & v_{n,n} \\ \end{bmatrix}

其中，vijv_{ij} 是向量 vi⃗\vec{v_i} 的第 jj 个坐标。这个行列式的绝对值就是由向量 v1⃗,v2⃗,...,vn⃗\vec{v_1}, \vec{v_2}, ..., \vec{v_n} 所形成的平行体的体积。

求解

暴力

首先有一个粗暴的做法单纯是根据定义求解的，虽然无法应用到那时有助于理解定义。

要求解行列式首先需要随机选择一行，为了方便说明不妨取第一行。那么在这一行的第 ii 个元素的贡献为 (−1)1+i×1×(-1)^{1+i}\times 1\times 不看这一行和这一列剩余的矩阵。

∣123456789∣=(−1)1+1×1×∣5689∣+(−1)1+2×2×∣4679∣+(−1)1+3×3×∣4578∣\begin{vmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 &8 &9\end{vmatrix}\\=(-1)^{1+1}\times 1\times \begin{vmatrix}5& 6\\8&9\end{vmatrix}+(-1)^{1+2}\times 2\times \begin{vmatrix}4&6\\7&9\end{vmatrix}+(-1)^{1+3}\times 3\times \begin{vmatrix}4&5\\7&8\end{vmatrix}

通过这个操作，我们就将这个行列式降阶了，接下来我们只需要一直进行递归操作直到行列式的阶成为 11 就好了。所以根据定义我们就可以在 O(n!)O(n!) 的时间复杂度内求解出 nn 阶行列式的值了。

优化

假设矩阵 AA 是一个上三角矩阵，那么 det⁡(A)=∏i=1nai,i\operatorname{det}(A)=\prod_{i=1}^{n}a_{i,i} 的值，求解的时间复杂度十分优秀为 O(n)O(n)，考虑是否可以使用高斯消元进行优化。

排列的性质

  • 定义如果 τ(p)\tau(p) 为奇数那么 pp 为奇排列，反之即为偶排列。
  • 对于一个 n(n≥2)n(n\geq2) 阶排列的所有排列情况，奇排列与偶排列的情况各有 12⋅n!\dfrac{1}{2}\cdot n! 种。
  • 将 pp 中两个不同的元素进行交换得到一个新的排列的过程叫对换操作，进行一次对换操作会改变序列的奇偶性。

矩阵性质

  • det⁡(A)=det⁡(AT)\operatorname{det}(A)=\operatorname{det}(A^T)，所以说所有的对列成立的性质均对行成立，反之亦然。
    带入排列的性质自行观察即可以得到。
  • 交换某 22 行或列，此时的 det⁡(A)\operatorname{det}(A) 需要乘以 −1-1。
    证明同上。
  • 根据上一行进行推论，如果有两行相同那么 det⁡(A)=0\operatorname{det}(A)=0。
    假设 s=det⁡(A)s=\operatorname{det}(A)，不妨设行 xx 与行 yy 相等，那么假设交换 x,yx,y 则有 det⁡(A)=−s\operatorname{det}(A)=-s 但是矩阵并未变化，所以 det⁡(A)=−det⁡(A)\operatorname{det}(A)=-\operatorname{det}(A) 就得到了 det⁡(A)=0\operatorname{det}(A)=0 是唯一解了。
  • 将 AA 的一行全部乘以 kk，那么 det⁡(A)\operatorname{det}(A) 也需要乘以 kk。
    考虑从使用定义求解行列式的值的角度进行解释。因为在求值是选择任意行计算的结果都是相同的，所以不妨假设我们刚好选择了全部乘以 kk 的那一行，使用乘法分配律将 kk 提出即可证明。
  • 根据上一行进行推论，如果有一行全部为 00 那么，那么 det⁡(A)=0\operatorname{det}(A)=0。
    假设 s=det⁡(A)s=\operatorname{det}(A)，那么不妨假设 xx 行全部为 00。将行 xx 全部乘以 kk 得到 det⁡(A)=s⋅k\operatorname{det}(A)=s\cdot k，可是矩阵并未变化所以 det⁡(A)=s\operatorname{det}(A)=s，因为 kk 为任意值所以得到 det⁡(A)=0\operatorname{det}(A)=0。
  • 如果行列式对应矩阵 AA 中有一行，是对应 22 个矩阵 B,CB,C 中分别的 22 行所有元素之和，那么有 det⁡(A)=det⁡(B)+det⁡(C)\det(A)=\det(B)+\det(C)。

∣a1,1a1,2⋯a1,na2,1a2,2⋯a2,n⋮⋮⋱⋮bi,1+ci,1bi,2+ci,2⋯bi,n+ci,n⋮⋮⋱⋮an,1an,2⋯an,n∣=∣a1,1a1,2⋯a1,na2,1a2,2⋯a2,n⋮⋮⋱⋮bi,1bi,2⋯bi,n⋮⋮⋱⋮an,1an,2⋯an,n∣+∣a1,1a1,2⋯a1,na2,1a2,2⋯a2,n⋮⋮⋱⋮ci,1ci,2⋯ci,n⋮⋮⋱⋮an,1an,2⋯an,n∣\begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ b_{i,1}+c_{i,1} &b_{i,2}+c_{i,2} &\cdots &b_{i,n}+c_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} = \begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ b_{i,1} &b_{i,2} &\cdots &b_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} + \begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ c_{i,1} &c_{i,2} &\cdots &c_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix}

  • 将某一行的的 kk 倍加到另外一行，不影响 det⁡(A)\operatorname{det}(A) 的值。
    结合前面的一些性质即可证明，十分显然。

高斯消元

考虑到将某一行的的 kk 倍加到另外一行不影响 det⁡(A)\operatorname{det}(A) 的值，可以直接使用高斯消元就可以求解了。同样还是高斯消元，用一个变量记录交换两行引起的符号改变。因为将一行的 𝑘𝑘 倍加到另一行上不影响答案，可以采用辗转相除的方式，将其他行的对应位置消成 00。

因为辗转相除法带一个 log⁡\log，所以总的时间复杂度为 O(n2log⁡W+n3)O(n^2\log W+n^3) 也就是 O(n3)O(n^3)，其中 WW 为矩阵的值域。

AC Code


#define debug
// #define tests
#include<bits/stdc++.h>
#define int long long 
#define x first
#define y second
using namespace std;
template<typename T=int> inline T read(){T x;cin>>x;return x;}
struct debug_{template<typename T>debug_&operator<<(T x){
#ifdef debug
cout<<x;
#endif
}}o;
const int N=605;
int n,a[N][N],mod;
void solve(){
	cin>>n>>mod;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	int flag=1;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			while(a[i][i]){
				int s=a[j][i]/a[i][i];
				for(int k=i;k<=n;k++){
					a[j][k]=(a[j][k]-s*a[i][k]+mod)%mod;
				}
				flag++;
				swap(a[i],a[j]);
			}
			flag++;
			swap(a[i],a[j]);
		}
	}
	int ans=1;
	for(int i=1;i<=n;i++){
		ans=(ans*a[i][i])%mod;
	}
	cout<<(ans*(flag%2?1:-1)+mod)%mod;
}
signed main(){
    #ifdef debug
    #else
    ios::sync_with_stdio(false),cin.tie(nullptr);
    #endif
    int T=1;
    #ifdef tests
    cin>>T;
    #endif
    while(T--) solve();
    return 0;
}