P7112题解&浅谈行列式
Hadtsti
·
·
题解
题意简述
模板题，求一个 n\times n(n\le 600) 的方阵的行列式模一个正整数 p(1\le p\le 10^9+7) 的值（p 不一定是质数）。
题目分析
这个题的最终代码其实很简单，重点在于过程。说实话，我在做这个题之前也就只知道个行列式的定义，只会暴力硬算。做了这个题才了解了行列式有那么多的好的性质，也算是开了开眼界吧。所以本文先介绍行列式本身再讲解题步骤。由于这篇文章本身也是我在学习 @Reywmp 大佬的 数学(5)——线性代数：行列式 一文之后写的，所以本文参考了这篇文章的内容，在此先膜拜大佬。另外我个人十分重视性质的证明过程，所以原来打算把自己写的几个性质的证明直接放到文中，后来考虑重要性不高以及篇幅问题就写到剪贴板里了，读者可以选择性看一看。（最好看看吧，毕竟我肝了将近两个小时）
定义
首先来看行列式的定义。对于一个 n\times n 的矩阵 A：
A=
\begin{bmatrix}
a_{1,1}& a_{1,2}& \cdots & a_{1,n} \\
a_{2,1}& a_{2,2}& \cdots & a_{2,n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{k,1}& a_{k,2}& \cdots & a_{k,n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n,1}& a_{n,2}& \cdots & a_{n,n}
\end{bmatrix}
它的行列式就是：
|A|=\sum_p (-1)^{\tau(p)}\prod_{k=1}^n a_{k,p_k}
其中 p 是 \{1,2,3,\cdots,n-1,n\} 的排列，\tau(p) 则是 p 中的逆序对个数。
形象化一点，你可以认为 \prod_{k=1}^n a_{k,p_k} 是由 p 决定的矩阵中两两不同行不同列的 n 个元素的乘积。如果 p 的逆序对个数为偶数，就把这个乘积加到总和里；反之，就从总和里把这个乘积减去。这样得到的总和就是矩阵的行列式。
那么这个看起来有点抽象的东西有什么实际用途呢？一个经典的例子是这样的：n\times n 的矩阵本身对应着 n 维欧式空间中的一个线性变换，而这个矩阵的行列式就对应着这个线性变换前后的“体积”之比。由于这部分不是特别重要，本文不过多展开。感兴趣的读者可以自行查询资料，如行列式的意义是什么？——知乎。
性质
行列式的性质有很多，在这里只介绍较为有用的几个。
1. 交换矩阵的两行或两列，行列式取反。
证明
2. 如果矩阵的某两行（列）相同，行列式为 0。
证明
3. 矩阵的某一行（列）的每个元素乘（除） m，行列式也乘（除） m。
证明
推论：由性质 2 和 3 可得到：若矩阵中有两行（列）的所有元素成比例，则其行列式为 0。
4. 若矩阵 A 中有一行（列）的每个元素都是 2 个矩阵 B 与 C 中对应的元素之和，其它行（列）的所有元素与 B、C 相同，则 |A|=|B|+|C|
证明
推论：若矩阵 A 中有一行（列）的每个元素都是 m 个矩阵 B_1,B_2,\cdots,B_n 中对应的元素之和，其它行（列）的所有元素与 B_1,B_2,\cdots,B_n 相同，则 |A|=|B_1|+|B_2|+\cdots+|B_n|。
5.把矩阵的某一行（列）乘上一个系数 m，加到另一行（列）上，矩阵行列式不变。
证明
6. 矩阵的行列式等于其任意一行（列）的每个元素及其代数余子式的乘积之和
先解释下什么是代数余子式。我们称一个矩阵去掉第 i 行和第 j 列后剩下的矩阵的行列式为其余子式 M_{i,j}，而代数余子式 A_{i,j}=(-1)^{i+j}\times M_{i,j}。
那么原命题就是对于第 i 行，有 \displaystyle|A|=\sum_{j=1}^na_{i,j}\times A_{i,j}；
对于第 j 列，有 \displaystyle|A|=\sum_{i=1}^na_{i,j}\times A_{i,j}
证明
解题步骤
本题直接暴力求值的时间复杂度为 O(n\times n!)，显然无法接受。
考虑之前的性质 1、3、5 中的操作，形式是不是有点熟悉？没错，它们就是矩阵的初等变换。而在高斯消元中，我们可以通过初等行变换进行消元将一个矩阵变为一个上三角矩阵。所以，我们只要能够求出消元后的上三角矩阵的行列式，就可以很简单地计算出原矩阵的行列式。
所以问题来了，怎么快速计算上三角矩阵的行列式？举个例子：
a_{1,1}& a_{1,2}& a_{1,3}&\cdots &a_{1,n-1}& a_{1,n} \\
0& a_{2,2}& a_{2,3}&\cdots &a_{2,n-1}& a_{2,n} \\
0& 0& a_{3,3}&\cdots &a_{3,n-1}& a_{3,n} \\
\vdots & \vdots&\vdots& \ddots &\vdots& \vdots \\
0& 0&0&\cdots &a_{n-1,n-1}& a_{n-1,n} \\
0& 0&0&\cdots &0& a_{n,n}
\end{bmatrix}
根据性质 6，有
\begin{vmatrix}
a_{1,1}& a_{1,2}& a_{1,3}&\cdots &a_{1,n-1}& a_{1,n} \\
0& a_{2,2}& a_{2,3}&\cdots &a_{2,n-1}& a_{2,n} \\
0& 0& a_{3,3}&\cdots &a_{3,n-1}& a_{3,n} \\
\vdots & \vdots&\vdots& \ddots &\vdots& \vdots \\
0& 0&0&\cdots &a_{n-1,n-1}& a_{n-1,n} \\
0& 0&0&\cdots &0& a_{n,n}
\end{vmatrix} =a_{n,n}\times A_{n,n}=a_{n,n}\times (-1)^{2n}\times M_{n,n}=a_{n,n}\times M_{n,n}
注意到：
M_{n,n}=
\begin{vmatrix}
a_{1,1}& a_{1,2}& a_{1,3}&\cdots &a_{1,n-2}& a_{1,n-1} \\
0& a_{2,2}& a_{2,3}&\cdots &a_{2,n-2}& a_{2,n-1} \\
0& 0& a_{3,3}&\cdots &a_{3,n-2}& a_{3,n-1} \\
\vdots & \vdots&\vdots& \ddots &\vdots& \vdots \\
0& 0&0&\cdots &a_{n-2,n-2}& a_{n-2,n-1} \\
0& 0&0&\cdots &0& a_{n-1,n-1}
\end{vmatrix}
那么就有（下图的 A_{n-1,n-1} 和 M_{n-1,n-1} 是相对原矩阵去掉第 n 行第 n 列的子矩阵而言的）：
M_{n,n}=
\begin{vmatrix}
a_{1,1}& a_{1,2}& a_{1,3}&\cdots &a_{1,n-2}& a_{1,n-1} \\
0& a_{2,2}& a_{2,3}&\cdots &a_{2,n-2}& a_{2,n-1} \\
0& 0& a_{3,3}&\cdots &a_{3,n-2}& a_{3,n-1} \\
\vdots & \vdots&\vdots& \ddots &\vdots& \vdots \\
0& 0&0&\cdots &a_{n-2,n-2}& a_{n-2,n-1} \\
0& 0&0&\cdots &0& a_{n-1,n-1}
\end{vmatrix}=a_{n-1,n-1}\times A_{n-1,n-1} =a_{n-1,n-1}\times (-1)^{2n-2}\times M_{n-1,n-1}=a_{n-1,n-1}\times M_{n-1,n-1}
发现了什么？是的，我们可以继续递归下去求解，最终会得出：
\begin{vmatrix}
a_{1,1}& a_{1,2}& a_{1,3}&\cdots &a_{1,n-1}& a_{1,n} \\
0& a_{2,2}& a_{2,3}&\cdots &a_{2,n-1}& a_{2,n} \\
0& 0& a_{3,3}&\cdots &a_{3,n-1}& a_{3,n} \\
\vdots & \vdots&\vdots& \ddots &\vdots& \vdots \\
0& 0&0&\cdots &a_{n-1,n-1}& a_{n-1,n} \\
0& 0&0&\cdots &0& a_{n,n}
\end{vmatrix}
=\prod_{i=1}^na_{i,i}
因此上三角矩阵的行列式是非常好求的，重点又回到了将原矩阵消元为上三角矩阵的过程。
注意到题目中 p 不一定是质数，这就代表不一定所有 a_{i,j} 都有逆元，不能使用高斯消元，应该采用其他方式。
回忆 \gcd 的辗转相除法，最终一个数变为 \gcd，另外一个数则变为 0，是不是可以用来消元？
答案是肯定的。我们选定需要消元的那一行，与其他行做辗转相除。因为辗转相除所用的操作都是矩阵的初等变换，所以根据消元后的矩阵的行列式可以运用性质 1、3、5 很方便计算出原矩阵的行列式。
最后看一下算法的时间复杂度。消元部分的时间复杂度为 O(n^3)；辗转相除的时间复杂度均摊，得到 O(n^2\log p)。所以算法总的时间复杂度记为 O(n^2(n+\log p))。另外由于消元过程中数据规模变小，所以消元部分常数也较小，对于 n=600 的数据和 2.0s 的时限是没问题的。
代码实现
#include<bits/stdc++.h>
using namespace std;
int n,a[610][610],res=1,w=1/*初等变换带来的系数*/,mod;
int main()
{
scanf("%d%d",&n,&mod);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
while(a[i][i])//没消掉就继续消
{
for(int rate=a[j][i]/a[i][i]/*“相除”，把商作为系数乘在第 i 行的元素上*/,k=i/*没消掉的元从 i 开始*/;k<=n;++k)
a[j][k]=(a[j][k]-1ll*rate*a[i][k]%mod+mod)%mod;//在消掉 a[j][i] 的同时它的整行元素都要进行同样操作
swap(a[i],a[j]);//“辗转”
w=-w;//计算系数
}
swap(a[i],a[j]);//“辗转”
w=-w;//计算系数
}
for(int i=1;i<=n;i++)
res=1ll*a[i][i]*res%mod;//计算上三角矩阵的行列式
res=(1ll*res*w%mod+mod)%mod;//一定要乘上系数！！！
printf("%d",res);
return 0;
}
由于本文写的时间跨度比较长，不可避免地存在错误和不足，欢迎大家指出！
update
本文最初发表于 2023.6.28，后自己发现文中的几处笔误，故于 2023.8.9 重新修改上传。