行列式求值
这是一个让你掉头发的模板题
行列式的定义
行列式 (\(\texttt{Determinant}\)) 是一个函数定义，取值是一个标量。
对一个 \(n\times n\) 的矩阵 \(A\)（\(n\) 阶方阵），其 \(n\) 阶行列式写作 \(\det(A)\) 或者 \(|A|\)，定义为：
\[\det(A)=|A|=\sum_p(-1)^{\tau(p)}\prod_{i=1}^n a_{i,p_i}
\]
\(p\) 表示一个排列，所有可能的 \(p\) 则是 \(1\) 到 \(n\) 这 \(n\) 个数的全排列。 \(\tau(p)\) 表示一个排列 \(p\)逆序对个数 。
2阶矩阵的行列式：
\[\begin{vmatrix}a & b \\c & d\end{vmatrix}=ad-bc
\]
3阶矩阵的行列式：
\[\begin{vmatrix}a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} &a_{23} \\a_{31} & a_{32} & a_{33}\end{vmatrix}=a_{11} a_{22} a_{33} + a_{12} a_{23} a_{31} + a_{13} a_{21} a_{32} - a_{13} a_{22} a_{31} - a_{11} a_{23} a_{32} - a_{12}a_{21}a_{33}
\]
\[\begin{vmatrix}18 & 5 & 1 \\12 & 2 &3 \\4& 2 & 1\end{vmatrix}
\]
我们今天的问题，仅限于如何把行列式的值求出来
前置知识
\(\tau(p)\)性质
我们发现 \(\tau(p)\) 的奇偶性对行列式求值起到了很大的影响，所以我们需要了解排列的奇偶性相关。
我们约定：如果 \(\tau(p)\) 为奇数，则 \(p\) 为一个奇排列，否则是一个偶排列；
对于排列 \(p\) 我们交换其中的 \(2\) 个元素，其余元素不边，会得到一个新的排列，这种操作叫 对换 ；
一次对换会改变排列的奇偶性(这是我们需要用到的定理)
证明如下：
设排列p(1到m)中，需要交换的两个元素分别为\(p_l和p_r\)，令\(n=r-l+1\)
显然，交换\(p_l和p_r\)不会改变\(p_l和p_r\)与\([1,l-1]和[r+1,m]\)中的元素组成逆序对，那么我们只需要考虑[l,r]中产生的影响即可
我们对\(p_l,p_{l+1},p_{l+2}……p_{r}\)进行离散化（把这个子排列变成一个1到n的排列)，例如：\(p[l:r]=[2,5,4]则p'[l:r]=[1,3,2]\)，其中p[l]在离散化后的排列中，大小为x，p[r]大小为y
我们发现，交换前，子序列中除\(p_l\)外，与\(p_l\)能构成\(n-x\)个逆序对，除\(p_r\)外，与\(p_r\)能构成\(y-1\)个逆序对，考虑x和y产生逆序对的情况后，加起来则是:\((n-x)+(y-1)-[x>y]\)
交换后，子序列中除\(p_l\)外，与\(p_l\)能构成\(x-1\)个逆序对，除\(p_r\)外，与\(p_r\)能构成\(n-y\)个逆序对，考虑x和y产生逆序对的情况后，加起来则是:\((x-1)+(n-y)-[y>x]\)
交换前后，相差的逆序对个数为\((n-x)+(y-1)-[x>y]-(x-1)-(n-y)+[y>x]=2n-2x-2y+2±1\)对，显然为奇数（±1产生的原因：\([x>y]和[y>x]\)中间有且仅有一个会被满足，所以\([y>x]-[x>y]\)的值为±1)
行列式性质1：
交换对应矩阵的 \(2\) 行（列），行列式的值取反
\(\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\\\ a_{k,1} &a_{k,2} &\cdots &a_{k,n}\\\ a_{k+1,1} &a_{k+1,2} &\cdots &a_{k+1,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\\\ a_{k+1,1} &a_{k+1,2} &\cdots &a_{k+1,n}\\\ 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{vmatrix}\)
(注意右边的矩阵，只有中间那两行是换了位置的，其余都没换位置)
证明如下：
设左边的行列式为A，右边为B求行列式的式子长这样：
\[\det(A)=|A|=\sum_p(-1)^{\tau(p)}\prod_{i=1}^n a_{i,p_i}
\]
我们对上面的式子做一点细微的修改，把它改成求\(det(B)\)
我们能不能构造一个排列q，使得排列q是利用某种神秘力量，从排列p转化而来，这样就能用a的值来代替b了？
就像这样：
\[\det(B)=\sum_p(-1)^{\tau(p)}\prod_{i=1}^n b_{i,p_i} \ ?\ \sum_q(-1)^{\tau(q)}\prod_{i=1}^n a_{i,q_i}
\]
当然可以。p和q的区别，仅在于第k位和第k+1位被换了位，这样就有\(b_{i,p_i}=a_{i,q_i}\)了！代价是\(\tau(p)=-\tau(q)\)
则有：
\[\det(B)=\sum_p(-1)^{\tau(p)}\prod_{i=1}^n b_{i,p_i} = \sum_q(-1)^{\tau(p)-1}\prod_{i=1}^n a_{i,p_i}=-det(A)
\]
行列式性质2：
行列式的行（列）所有元素等比例变化，则行列式的值也等比例变化：
$\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\\ k\times a_{i,1} &k\times a_{i,2} &\cdots &k\times a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} =k\times \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\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} $
我们用乘法分配律，即可证明这个性质
行列式性质3：
如果行列式对应矩阵 \(A\) 中有一行（列），是对应 \(2\) 个矩阵 \(B,C\) 中分别的 \(2\) 行（列）所有元素之和。那么有 \(\det(A)=\det(B)+\det(C)\)；
$\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} $
我们可以对每个\(b_i,?+c_i,\)进行乘法分配律，来完成证明
行列式性质4：
由性质1和性质2可以推出：
如果一个矩阵存在两行（列）成比例则 \(\det(A)=0\)，则有：
$\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\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ k\times a_{i,1} &k\times a_{i,2} &\cdots &k\times a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix}=0 $
证明如下：
$\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\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ k\times a_{i,1} &k\times a_{i,2} &\cdots &k\times a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix}=k\times \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\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{i,1} & a_{i,2} &\cdots & a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} $
设右边的矩阵为\(A'\)，由于存在两行相同，我们交换两行后可以得到\(-A'\)，且\(-|A'|=|-A'|\)
得\(|A'|=0,|A|=0\times |A'|=0\)
行列式性质5：
把一个矩阵的一行（列）的值全部乘一个常数加到另一行（列）上，行列式值不变。\((6)\)
$\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\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{j,1}+k\times a_{i,1} &a_{j,2}+k\times a_{i,2} &\cdots &a_{j,2}+k\times a_{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\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{j,1} &a_{j,2} &\cdots &a_{j,2}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} $
证明也很简单，根据 \((3)\) 有：
$\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\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{j,1}+k\times a_{i,1} &a_{j,2}+k\times a_{i,2} &\cdots &a_{j,2}+k\times a_{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\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{j,1} &a_{j,2} &\cdots &a_{j,2}\\ \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\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ k\times a_{i,1} &k\times a_{i,2} &\cdots &k\times a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} $
$\because $行列式性质4
$\therefore \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\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{j,1}+k\times a_{i,1} &a_{j,2}+k\times a_{i,2} &\cdots &a_{j,2}+k\times a_{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\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{j,1} &a_{j,2} &\cdots &a_{j,2}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix}+0 $
行列式性质6：
如图所示：这是一个三角行列式
$\begin{vmatrix} \color{orange}a_{1,1} & \color{green}a_{1,2} &
\color{blue}a_{1,3} & \color{red}\cdots &\color{red}a_{1,n-1} &a_{1,n}\\ 0 &
\color{green}a_{2,2} & \color{blue}a_{2,3} & \color{red}\cdots
&\color{red}a_{2,n-1} &a_{2,n}\\ 0 &0 &\color{blue} a_{3,3} &\color{red}
\cdots &\color{red}a_{3,n-1} &a_{3,n}\\ \color{red}\vdots & \color{red}\vdots
& \color{red}\vdots & \color{red}\ddots &\color{red} \vdots &\vdots\\ 0 &0 &
0 & \color{red}\cdots &\color{red}a_{n-1,n-1} &a_{n,n-1}\\ 0 & 0 & 0 & \cdots
&0 &a_{n,n}\\ \end{vmatrix} $
三角行列式的值非常好求： \(|A|=\displaystyle\prod_{i=1}^na_{i,i}\)
这一条式子很好证明：
我们考虑一个情况，当一个矩阵任意一个位置出现 \(0\)，其对行列式的影响非常大。
因为我们考虑公式中 \(\displaystyle\prod_{i=1}^n a_{i,p_i}\) 一项，一旦选到 \(0\) 整个 \(p\) 在
\(\displaystyle \sum_p\) 中就没有贡献了。
在求行列式值时，序列p不指向对角线上元素时，是不是一定会选到0呢？
行列式求值
下面开始进入正题
我会暴力！
直接根据定义计算，行列式求值是 \(\Theta(n\times n!)\) 的。
有了上面七个性质，我们有办法加快运算吗？
消元
我们考虑一个情况，当一个矩阵任意一个位置出现 \(0\)，其对行列式的影响非常大。
因为我们考虑公式中 \(\displaystyle\prod_{i=1}^n a_{i,p_i}\) 一项，一旦选到 \(0\) 整个 \(p\) 在
\(\displaystyle \sum_p\) 中就没有贡献了。
下面进入大胆猜想：
我们能不能对原行列式A进行一系列的变换，使得它变成一个三角行列式，像下面这样？
\(A=\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} & \cdots &a_{1,n}\\\ a_{2,1} &
a_{2,2} & a_{2,3} & \cdots &a_{2,n}\\\ a_{3,1} & a_{3,2} & a_{3,3} & \cdots
&a_{3,n}\\\ \vdots & \vdots & \vdots & \ddots & \vdots\\\ a_{n,1} & a_{n,2} &
a_{n,3} & \cdots &a_{n,n}\\\ \end{bmatrix}\) \(\Rightarrow\) \(\begin{bmatrix} a’_{1,1}
& a‘_{1,2} & a’_{1,3} & \cdots &a‘_{1,n}\\\ 0 & a’_{2,2} & a‘_{2,3} & \cdots
&a_{2,n}\\\ 0 & 0 & a’_{3,3} & \cdots &a‘_{3,n}\\\ \vdots & \vdots &
\vdots & \ddots & \vdots\\\ 0 & 0 & 0 & \cdots &a’_{n,n}\\\ \end{bmatrix}\)
这个三角行列式，怎么和高斯消元，完成加减消元时的矩阵很像？
我们能不能像高斯消元中加减消元一样，利用行列式第\(i\)行的信息，把第\(i+1\)到\(n\)行中\(a[][i]\)变为0
当然可以！
代码长这样：
double sol()
{
double res=1;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;++j)
{
double div=a[j][i]/a[i][i];
for(int k=i;k<=n;++k)
{
a[j][k]=(a[j][k]-div*a[i][k]);
}
}
}
for(int i=1;i<=n;i++) res*=a[i][i];
return res;
}
但是，此题要求你取模，模的数甚至不是质数？还乘不了逆元？
出现了一点小问题
我们可以把除or乘逆元，换成辗转相除？像这样：
\[\begin{vmatrix}18 & 5 & 1 \\12 & 2 &3 \\4& 2 & 1\end{vmatrix}=-\begin{vmatrix}12 & 2 &3 \\18 & 5 & 1 \\4& 2 & 1\end{vmatrix}=-\begin{vmatrix}12 & 2 &3 \\6 & 3 & -2 \\4& 2 & 1\end{vmatrix}=\begin{vmatrix}6 & 3 & -2 \\12 & 2 &3 \\4& 2 & 1\end{vmatrix}=\begin{vmatrix}6 & 3 & -2 \\0 & -4 &-1 \\4& 2 & 1\end{vmatrix}
\]
我们成功在\(a[2][1]\)处制造了一个0出来！！
通过这样的方式，我们就可以在p不为质数的时候，把这个行列式安全地化为三角行列式
消元操作是 \(\Theta(n^3)\) 的，辗转相除法是 \(\Theta(\log p)\)的，因为辗转相除和消元每次必然使得数变小，势能只会减少，所以这个是均摊到 \(\Theta(n^2)\) 的，最终复杂度为 \(\Theta(n^2\log
n+n^3)\)。
代码
#include<bits/stdc++.h>
#define INL inline
#define ll long long
using namespace std;
const int N=605;
int n,a[N][N],MOD;
INL int read()
{
int x=0,w=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x*w;
}
INL int sol()
{
int res=1,w=1;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;++j)
{
while(a[i][i])
{
int div=a[j][i]/a[i][i];
for(int k=i;k<=n;++k)
{
a[j][k]=(a[j][k]-1ll*div*a[i][k]%MOD+MOD)%MOD;
}
swap(a[i],a[j]);w=-w;
}//对第 i 行和第 j 行做辗转相减。
swap(a[i],a[j]);w=-w;
}
}
for(int i=1;i<=n;i++)res=1ll*a[i][i]*res%MOD;
res=1ll*w*res;
return (res+MOD)%MOD;
}
int main()
{
n=read(),MOD=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=read();
int ans=sol();printf("%d\n",ans);
return 0;
}
