P7112 题解

题意简述

模板题，求一个 \(n\times n(n\le 600)\) 的方阵的行列式模一个正整数 \(p(1\le p\le 10^9+7)\) 的值（\(p\) 不一定是质数）。

题目分析

这个题的最终代码其实很简单，重点在于过程。说实话，我在做这个题之前也就只知道个行列式的定义，只会暴力硬算。做了这个题才了解了行列式有那么多的好的性质，也算是开了开眼界吧。所以本文先介绍行列式本身再讲解题步骤。由于这篇文章本身也是我在学习 @Reywmp 大佬的 数学(5)——线性代数：行列式 一文之后写的，所以本文参考了这篇文章的内容，在此先膜拜大佬。另外我个人十分重视性质的证明过程，所以把自己写的几个性质的证明直接放到了文中，读者可以选择性看一看。（最好看看吧，毕竟我肝了将近两个小时）

定义

首先来看行列式的定义。对于一个 \(n\times n\) 的矩阵 \(A\)：

它的行列式就是：

其中 \(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. 交换矩阵的两行或两列，行列式取反。

证明：交换矩阵的第 \(i\) 行与第 \(j\) 行，对行列式产生的实际影响是将原先的每一个 \(\prod_{k=1}^n a_{k,p_k}\) 中，原来的 \(a_{i,p_i}\) 换到了第 \(j\) 行，而原来的 \(a_{j,p_j}\) 换到了第 \(i\) 行，对应的也就是将每个排列 \(p\) 中的 \(p_i\) 与 \(p_j\) 两项交换。这一交换的作用则是改变了 \(\tau(p)\)，也就是说，我们只需要证明交换后的排列 \(p'\) 满足 \(\tau(p')\) 与 \(\tau(p)\) 奇偶性不同即可。

不妨设 \(i<j\)。交换 \(p_i\) 与 \(p_j\) 使 \(\tau(p)\) 产生的变化来自于：

1.\(p_i\) 与 \(p_j\) 大小关系必然变化（这是因为 \(p\) 是 \(\{1,2,3,\cdots,n\}\) 的排列，所以 \(p_i ≠ p_j\)），\(\tau(p)\) 加 1 或减 1。

2.\(p_i\) 与 \(p_k\)（\(\forall k\in(i,j)\)）的大小关系发生的变化，设满足 \(p_i<p_k\) 的 \(k\) 有 \(a\) 个，则 \(p_k<p_i\) 的 \(k\) 有 \(j-i+1-a\) 个，\(\tau(p)\) 增加或减少 \(|j-i+1-2a|\)。

3.\(p_j\) 与 \(p_k\)（\(\forall k\in(i,j)\)）的大小关系发生的变化，设满足 \(p_j<p_k\) 的 \(k\) 有 \(b\) 个，则 \(p_k<p_j\) 的 \(k\) 有 \(j-i+1-b\) 个，\(\tau(p)\) 增加或减少 \(|j-i+1-2b|\)。

注意到 \(|j-i+1-2a|\) 和 \(|j-i+1-2b|\) 与 \(j-i+1\) 奇偶性均相同，那么就有 \(|j-i+1-2a|\pm|j-i+1-2b|\) 必定为偶数。也就是说，上文的第 2、3 类大小关系的改变不会使 \(\tau(p)\) 的奇偶性产生改变，因此能够使得 \(\tau(p)\) 奇偶性改变的只有第 1 类改变。这就表明 \(\tau(p)\) 的奇偶性必将发生变化。

交换列的情况类似。

2. 如果矩阵的某两行（列）相同，行列式为 0。

证明：交换矩阵相同的两行（列），矩阵不变，那么行列式也不变。但是由性质 1 得到前后的行列式是相反数，这就推出行列式为 0。

3. 矩阵的某一行（列）的每个元素乘（除） \(m\)，行列式也乘（除） \(m\)。

证明：设矩阵的第 \(i\) 行乘了 \(m\)，那么 \(|A|=\sum_p (-1)^{\tau(p)}\prod_{k=1}^n a_{k,p_k}\) 中的每一个 \(a_{i,p_i}\) 都乘上了 \(m\)。所以 \(|A|\) 也乘上了 \(m\)。

推论：由性质 2 和 3 可得到：若矩阵中有两行（列）的所有元素成比例，则其行列式为 0。

4. 若矩阵 \(A\) 中有一行（列）的每个元素都是 2 个矩阵 B 与 C 中对应的元素之和，其它行（列）的所有元素与 \(B\)、\(C\) 相同，则 \(|A|=|B|+|C|\)

证明：设为第 \(i\) 行，则 \(\forall j\in[1,n]\)，有 \(a_{i,j}=b_{i,j}+c_{i,j}\)，且 \(\forall x,y\in[1,n],x≠i\)，有 \(a_{x,y}=b_{x,y}=c_{x,y}\)

那么有：

\(\ \ \ \ \displaystyle|B|+|C|\)

\(\displaystyle=\sum_p (-1)^{\tau(p)}\prod_{k=1}^n b_{k,p_k}+\sum_p (-1)^{\tau(p)}\prod_{k=1}^n c_{k,p_k}\)

\(\displaystyle=\sum_p (-1)^{\tau(p)}[(\prod_{k=1}^{i-1} b_{k,p_k})\times(b_{i,p_i})\times(\prod_{k=i+1}^n b_{k,p_k})]+\sum_p (-1)^{\tau(p)}[(\prod_{k=1}^{i-1} c_{k,p_k})\times(c_{i,p_i})\times(\prod_{k=i+1}^n c_{k,p_k})]\)

\(\displaystyle=\sum_p (-1)^{\tau(p)}[(\prod_{k=1}^{i-1} a_{k,p_k})\times(b_{i,p_i})\times(\prod_{k=i+1}^n a_{k,p_k})+(\prod_{k=1}^{i-1} a_{k,p_k})\times(c_{i,p_i})\times(\prod_{k=i+1}^n a_{k,p_k})]\)

\(\displaystyle=\sum_p (-1)^{\tau(p)}[(\prod_{k=1}^{i-1} a_{k,p_k})\times(b_{i,p_i}+c_{i,p_i})\times(\prod_{k=i+1}^n a_{k,p_k})]\)

\(\displaystyle=\sum_p (-1)^{\tau(p)}[(\prod_{k=1}^{i-1} a_{k,p_k})\times(a_{i,p_i})\times(\prod_{k=i+1}^n a_{k,p_k})]\)

\(\displaystyle=\sum_p (-1)^{\tau(p)}\prod_{k=1}^n a_{k,p_k}\)

\(\displaystyle=|A|\)

推论：若矩阵 \(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\)，加到另一行（列）上，矩阵行列式不变。

证明：设第 \(j\) 行乘上 \(m\) 后加到第 \(i\) 行上，也就是：

由性质 4 ，

由性质 2、3 的推论，

则

证毕。

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}\)。

证明：以第 \(i\) 行为例，由性质 4 的推论，得到：

其中，有

显然，\(\displaystyle(-1)^{\tau(p)}\prod_{k=1}^n a_{k,p_k}\) 只有当 \(p_i=j\) 时才不为0，也就是说可以认为此时 \(p_i\) 固定为 \(j\) 。那么 \(p\) 现在不固定的实际上是 \(\{1,2,\cdots,j-1,j+1,\cdots,n\}\) 的排列，设为 \(p'\)。至于前面的 \((-1)^{\tau(p)}\)，我们可以把 \(\tau(p)\) 分解为与 \(i\) 有关的逆序对数量 \(m\) 和 \(\tau(p')\)。 注意到与 \(i\) 有关的逆序对数量就是满足以下两条件之一的整数 \(k\) 的数量：

• \(k<i,p_k>j\)
• \(k>i,p_k<j\)

若 \(i<j\)，考虑原始排列 \(p=\{1,2,3,\cdots,i-2,i-1,j,\cdots,n\}\)，此时满足 \(\forall k<i,p_k<j\)， \(m=(j-1)-(i-1)=j-i\)。若 \(i>j\)，考虑原始排列 \(p=\{1,\cdots,j,i+1,i+2,\cdots,n-2,n-1,n\}\)，此时满足 \(\forall k>i,p_k>j\)，则 \(m=(i-1)-(j-1)=i-j\)。而每次构造一个新的合法排列（即满足 \(p_i=j\) 的排列）时需要交换 \(i\) 之前的某数和 \(i\) 之后的某数，设分别为 \(p_{i_1}\) 和 \(p_{i_2}(i_1<i<i_2)\)，那么分以下几种情况：

1. \(p_{i_1}<j\)，\(p_{i_2}<j\) 或 \(p_{i_1}>j\)，\(p_{i_2}>j\)

   ​ \(m\) 不变。

2. \(p_{i_1}<j\)，\(p_{i_2}>j\)

   ​ \(m\) 增加 2。

3. \(p_{i_1}>j\)，\(p_{i_2}<j\)

   ​ \(m\) 减少 2。

这就表明，每个合法排列的 \(k\) 的奇偶性与原始排列相同，也就是 \(m≡|i-j|≡i+j(\mod2)\)，所以 \((-1)^{\tau(p)}=(-1)^{{\tau(p')}+m}=(-1)^{\tau(p')}\times(-1)^m=(-1)^{\tau(p')}\times(-1)^{i+j}\)。

那么就有

证毕。

解题步骤

本题直接暴力求值的时间复杂度为 \(O(n\times n!)\)，显然无法接受。

考虑之前的性质 1、3、5 中的操作，形式是不是有点熟悉？没错，它们就是矩阵的初等变换。而在高斯消元中，我们可以通过初等行变换进行消元将一个矩阵变为一个上三角矩阵。所以，我们只要能够求出消元后的上三角矩阵的行列式，就可以很简单地计算出原矩阵的行列式。

所以问题来了，怎么快速计算上三角矩阵的行列式？举个例子：

根据性质 6，有

注意到：

那么就有（下图的 \(A_{n-1,n-1}\) 和 \(M_{n-1,n-1}\) 是相对原矩阵去掉第 \(n\) 行第 \(n\) 列的子矩阵而言的）：

发现了什么？是的，我们可以继续递归下去求解，最终会得出：

因此上三角矩阵的行列式是非常好求的，重点又回到了将原矩阵消元为上三角矩阵的过程。

注意到题目中 \(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;
}

由于本文写的时间跨度比较长，不可避免地存在错误和不足，欢迎大家指出！

本栏目推荐文章
• AT_arc125_c [ARC125C] LIS to Original Sequence 题解
• P5321 [BJOI2019] 送别 题解--zhengjun
• P9007 [入门赛 #9] 最澄澈的空与海 (Hard Version) 题解
• P2198 杀蚂蚁 题解
• P3243 [HNOI2015] 菜肴制作 题解
• AT_abc243_g [ABC243G] Sqrt题解
• AT_abc243_g [ABC243G] Sqrt题解
• P9754 题解
• AT_arc167_e 题解
• AT_agc054_c 题解

题解 P7112 7112题解p7112 7112 p7112 行列式 行列 模板p7112 p-th p-asemi p-tuning p-core p-limit ku3p-ku