本文同时也作为P6178的题解。
1.行列式基础
对于一个矩阵 A[1...n][1...n] ,其行列式为
\det(A)=\sum\limits_{P}(-1)^{\mu(P)}\prod\limits_{i=1}^nA[i][p_i]
(枚举排列 P[1...n] ,其中 \mu(P) 为排列 P 的逆序对数)
( \det(A) 又作 |A| )
也就是说在每一行挑一个乘起来,然后再拿逆序对有关的东西做系数。
直接按照定义计算,复杂度是 O(n!·n) 的。
知道了下面几条性质之后,我们就能快速计算行列式了。
这个比较显然,因为 P 除了对角线之外没有别的选择,而对角线乘积为 1。
类似的,上三角矩阵和下三角矩阵的行列式都是对角线乘积。
(根据逆序对感性理解即可)
我们考虑对于每个排列,这一次交换只会影响乘积组前面的逆序对系数。
对于任意一个序列,交换两个数对于逆序对个数的影响必定为奇数(可以自己讨论一下)。
所以逆序对系数全部都改变,即变号。
- (2) 若某一行乘以 t ,行列式就也乘以 t 。
这个比较好理解,因为这一行选且只选一个嘛。
\begin{vmatrix}a+a'&b+b'\\c&d\end{vmatrix}=\begin{vmatrix}a&b\\c&d\end{vmatrix}+\begin{vmatrix}a'&b'\\c&d\end{vmatrix}
还是因为一行选且只选一个,然后乘法分配律就好了。
(2,3合起来就是行的线性性)
这个证明比较巧妙 : 考虑交换相同的这两行,根据(1)得行列式变号。
但是矩阵并没有实质的改变,行列式不变,所以行列式的值只能是 0.
- (5) 用矩阵的一行加上另一行的倍数,行列式不变。
考虑构造(省略的部分表示不变):
欲证\begin{vmatrix}a&b&c\\.&.&.\\d&e&f\end{vmatrix}=\begin{vmatrix}a&b&c\\.&.&.\\d+ka&e+kb&f+kc\end{vmatrix}
首先构造一个\begin{vmatrix}a&b&c\\.&.&.\\a&b&c\end{vmatrix},根据(4)得其值为0.
又根据(2)得\begin{vmatrix}a&b&c\\.&.&.\\ka&kb&kc\end{vmatrix}也为0。
然后根据(3)得
\begin{vmatrix}a&b&c\\.&.&.\\d+ka&e+kb&f+kc\end{vmatrix}=\begin{vmatrix}a&b&c\\.&.&.\\d&e&f\end{vmatrix}+\begin{vmatrix}a&b&c\\.&.&.\\ka&kb&kc\end{vmatrix}=\begin{vmatrix}a&b&c\\.&.&.\\d&e&f\end{vmatrix}
其实我们上面证明的性质,就是为这个来打基础的。
我们消元的时候,只是用了 {交换两行, 某一行乘一个常数, 一行加上另一行的倍数} 三种操作。
那么,我们对于 A 进行消元,然后记录操作对于行列式的影响,最后得到上三角矩阵,行列式就是对角线乘积,如果消不出来那么返回 0。
最后再把影响逆回去即可。
2.矩阵树定理与部分扩展
(默认图中无自环)
给出一个无向无权图,设 A 为邻接矩阵, D 为度数矩阵( D[i][i]=节点 i 的度数,其他的无值)。
则基尔霍夫(Kirchhoff)矩阵即为 : K=D-A
然后令 K' 为 K 去掉第k行与第k列(k任意)的结果(n-1阶主子式),
~~证明不会。感兴趣的同学可以自行百度。~~
**例题** : [P4336 [SHOI2016]黑暗前的幻想乡](https://www.luogu.org/problemnew/show/P4336)
- ## 加权扩展
容易理解 : 带重边的情况,上面的经典矩阵树定理也是能够处理的。
根据乘法原理,对于某种生成树的形态,其贡献为**每条边重的次数的乘积**。
如果把重边次数理解成权值的话,那么矩阵树定理求的就是 : 所有生成树边权乘积的总和。
(这里注意度数矩阵变成了相邻边的权值和)
**例题** : [P3317 [SDOI2014]重建](https://www.luogu.com.cn/problem/P3317)
- ## 有向扩展
前面都是无向图,神奇的是有向图的情况也是可以做的。
(邻接矩阵 $A$ 的意义同有向图邻接矩阵)
那么现在的矩阵 $D$ 就要变一下了。
若 $D[i][i]=\sum\limits_{j=1}^nA[j][i]$ ,即**到该点的边权总和(入)**。
此时求的就是**外向树** (从根向外)
若 $D[i][i]=\sum\limits_{j=1}^nA[i][j]$ ,即从**从该点出发的边权总和(出)**。
此时求的就是**内向树** (从外向根)
(如果考场上不小心忘掉了,可以手玩小样例)
(同样可以加权!)
此外,既然是有向的,那么就需要**指定根**。
前面提过要任意去掉第 $k$ 行与第 $k$ 列,是因为无向图所以不用在意谁为根。
在有向树的时候需要理解为指定根,结论是 : 去掉哪一行就是那一个元素为根。
**例题** : [P4455 [CQOI2018]社交网络](https://www.luogu.com.cn/problem/P4455) (内向树)
本题就是外向树,下面给出代码(出乎意料,跑的还挺快)。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define mod 1000000007
#define Maxn 305
using namespace std;
ll powM(ll a,int t=mod-2)
{
ll ans=1;
while(t){
if (t&1)ans=ans*a%mod;
a=a*a%mod;t>>=1;
}return ans;
}
int n,m;
ll *a[Maxn],_a[Maxn][Maxn];
ll det(ll **a)
{
ll ans=1;bool tr=0;
for (int j=1;j<n;j++){
for (int i=j;i<n;i++)
if (a[i][j]){
if (i!=j){
swap(a[i],a[j]);
tr=!tr;
}break;
}
if (a[j][j]==0)return 0;
ans=ans*a[j][j]%mod;
ll t=powM(a[j][j]);
for (int k=j;k<n;k++)a[j][k]=t*a[j][k]%mod;
for (int i=j+1;i<n;i++){
t=mod-a[i][j];
for (int k=j;k<n;k++)
a[i][k]=(a[i][k]+t*a[j][k])%mod;
}
}return tr? (mod-ans)%mod : ans;
}
int op;
int main()
{
scanf("%d%d%d",&n,&m,&op);
for (int i=1;i<=n;i++)a[i]=_a[i];
for (int i=1,f,t,w;i<=m;i++){
scanf("%d%d%d",&f,&t,&w);
if (f==n)f=1;else if (f==1)f=n;
if (t==n)t=1;else if (t==1)t=n;
if (op==1){
a[f][t]=(a[f][t]-w+mod)%mod;
a[t][t]=(a[t][t]+w)%mod;
}else {
a[f][t]=(a[f][t]-w+mod)%mod;
a[t][t]=(a[t][t]+w)%mod;
a[t][f]=(a[t][f]-w+mod)%mod;
a[f][f]=(a[f][f]+w)%mod;
}
}printf("%lld",det(a));
return 0;
}
```