矩阵树定理
行列式
定义
行列式是矩阵树定理的一个重要的前置知识。
行列式是一个 \(n*n\) 的矩阵，整体能够计算出一个数值，比如：
二阶行列式：
\[
\begin{vmatrix}
x & y \\
z & w
\end{vmatrix} = xw - yz
\]
三阶行列式：
\[
\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_{11} - a_{12}a_{21}a_{13} - a_{11}a_{23}a_{12}
\]
具体来说：
\[\det(A) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^{n} a_{i,\sigma(i)}\]
其中：
- \(det(A)\) 表示对于行列式 \(A\) 求值。
- \(S_n\) 表示 \(1,2,\cdots,n\) 的全排列
- \(sgn(\sigma)\) 表示序列 \(\sigma\) 的逆序对数量
性质
但是目前我们不需要知道这个行列式具体有什么用，但是他有一些性质：
1. 代数余子式展开
\[\det(A) = \sum_{j=1}^{n} (-1)^{i+j} a_{ij} M_{ij} \quad (\text{按第 } i \text{ 行展开})\]
这列的 \(M_{ij}\) 表示行列式 \(A\) 删去第 \(i\) 行 \(j\) 列 之后的值。
如果这里 \(i\) 取 \(1\) 那么可以得到： \(\det(A) = \sum_{j=1}^{n} (-1)^{1+j} a_{1j} M_{1j}\)
2. 行交换变号
数学符号表示：
\[
\begin{vmatrix}
\vdots & \vdots & & \vdots \\
a_{i1} & a_{i2} & \cdots & a_{in} \\
\vdots & \vdots & & \vdots \\
a_{j1} & a_{j2} & \cdots & a_{jn} \\
\vdots & \vdots & & \vdots
\end{vmatrix}
= -\begin{vmatrix}
\vdots & \vdots & & \vdots \\
a_{j1} & a_{j2} & \cdots & a_{jn} \\
\vdots & \vdots & & \vdots \\
a_{i1} & a_{i2} & \cdots & a_{in} \\
\vdots & \vdots & & \vdots
\end{vmatrix}
\]
3. 行倍乘
数学符号表示：
\[
\begin{vmatrix}
\vdots & \vdots & & \vdots \\
a_{i1} & a_{i2} & \cdots & a_{in} \\
\vdots & \vdots & & \vdots \\
a_{j1} & a_{j2} & \cdots & a_{jn} \\
\vdots & \vdots & & \vdots
\end{vmatrix}
= -\begin{vmatrix}
\vdots & \vdots & & \vdots \\
a_{i1} & a_{i2} & \cdots & a_{in} \\
\vdots & \vdots & & \vdots \\
a_{i1}*k+a_{j1} & a_{i2}*k+a_{j2} & \cdots & a_{in}*k+a_{jn} \\
\vdots & \vdots & & \vdots
\end{vmatrix}
\]
4. 三角形行列式
数学符号表示：
\[
\begin{vmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
0 & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & a_{nn}
\end{vmatrix} = a_{11} a_{22} \cdots a_{nn}
\]
（这些性质易证 绝对不是因为我不会证）
行列式求值
我们发现这个性质三和高斯消元相当之像对吧，因为对于一个方程的矩阵也满足这个性质。
所以我们考虑直接使用一个 高斯消元 套进去，然后最后得到一个三角形行列式，然后有直接套用三角形行列式的取值就可以了，时间复杂度 \(\mathcal O(N^3\log N)\) （这个 \(\log N\) 来自求除数逆元，如果对于实数行列式则没有）。
示例代码——实数行列式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | double det(int n){
double ans=1.0;
for(int i=1;i<n;i++){
int pos=i;
for(int j=i+1;j<=n;j++){
if(fabs(l[j][i])>fabs(l[pos][i]))
pos=j;
}
if(fabs(l[pos][i])<eps) return 0.0;
if(i!=pos) swap(l[i],l[pos]),ans*=-1;
for(int j=i+1;j<=n;j++){ // 消除l[j][i]
double t=l[j][i]/l[i][i];
for(int k=i;k<=n;k++){
l[j][k]=(l[j][k]-l[i][k]*t);
}
}
}
for(int i=1;i<=n;i++) ans*=l[i][i];
return ans;
}
|
但是对于 整数行列式+取模 的情况呢，如果取模的数是质数，倒是好说（费马小定理），但是如果题目想坑人，使用了类似 \(1e9\) 这样的模数，我们是不是还需要写一个 \(\texttt{exgcd()}\) 。
但是我们明确一下目标，对于两个数 \(a,b\) ，通过一个乘一个加到另一个数的办法，把另一个数变为 \(0\) ， 这不就是辗转相除法吗，对于 \(\gcd(a,b) = \gcd(b,a \mod b) = \gcd(b, a - \lfloor \frac{a}{b}\rfloor * b)\) ，此时哪一个乘的倍数就是 \(- \lfloor \frac{a}{b}\rfloor\) 。一看就满足这个性质，所以我们可以得到一个不需要求逆元的版本。
示例代码——整数取模行列式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | int det(int n){
int ans=1;
for(int i=1; i<=n; i++) {
for(int j=i+1; j<=n; j++) {
// a: l[i] b: l[j]
while(l[j][i]!=0){
int t=l[i][i]/l[j][i];
for(int k=i; k<=n; k++)
l[i][k]=( (l[i][k]-t*l[j][k]) %mod+mod)%mod;
swap(l[i],l[j]), ans*=-1;
}
}
}
for(int i=1; i<=n; i++) ans=ans*l[i][i]%mod;
return (ans%mod+mod)%mod;
}
|
矩阵树定理
矩阵树定理 解决的问题就是一个图的生成树个数，其分为两种情况：
1. 无向图
定义 Laplace矩阵 为 \(L = D - A\) 。
其中 \(D\) 为度数矩阵，满足 \(D_{ii}=du_i\)， \(A\) 为邻接矩阵。
比如对于有边 \((1,2),(2,3),(1,3)\) 的图，其 Laplace矩阵 为：
\[
L =\begin{vmatrix}
2 & -1 & -1 \\
-1 & 2 & -1 \\
-1 & -1 & 2 \\
\end{vmatrix}
\]
然后矩阵树定理说明了这个图的生成树个数为其 Laplace矩阵 去掉任意一行一列之后的行列式值。比如现在这个矩阵：
\[
L =\begin{vmatrix}
2 & -1 & -1 \\
-1 & 2 & -1 \\
-1 & -1 & 2 \\
\end{vmatrix}
\to \begin{vmatrix}
2 & -1 \\
-1 & 2 \\
\end{vmatrix} =3
\]
可以发现这个图的生成树个数就是 \(3\) 。
但是对于重边呢，其实完整的矩阵树定理是这样的：
矩阵树定理
对于一个无向图，每一个边有一个边权 \(w_i\),
满足去掉一行一列之后的 Laplace矩阵 值为 \(\sum_{T}\prod_{e\in T} w_{e}\)
所以只要是求所有生成树权值乘积之和的问题，都可以转化为矩阵树定理，而生成树个数就是当 \(w_i\) 都为 \(1\) 时的特殊情况。
示例代码——整数取模
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | struct Matrix_Tree{
int l[N][N];
void add(int x,int y,int z) {
l[x][x]+=z, l[y][y]+=z;
l[x][y]-=z, l[y][x]-=z;
}
void clear(){
memset(l,0,sizeof l);
}
int det(int n){
n--; // 去除最后一行和最后一列
int ans=1;
for(int i=1; i<=n; i++) {
for(int j=i+1; j<=n; j++) {
// a: l[i] b: l[j]
while(l[j][i]!=0){
int t=l[i][i]/l[j][i];
for(int k=i; k<=n; k++)
l[i][k]=( (l[i][k]-t*l[j][k]) %mod+mod)%mod;
swap(l[i],l[j]), ans*=-1;
}
}
}
for(int i=1; i<=n; i++) ans=ans*l[i][i]%mod;
return (ans%mod+mod)%mod;
}
};
Matrix_Tree T;
|
示例代码——实数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | struct Matrx_Tree{
double l[N][N];
void add(int x,int y,double z){
l[x][y]-=z,l[y][x]-=z;
l[x][x]+=z,l[y][y]+=z;
}
double det(int n){
n--; // 删去最后一列
double ans=1.0;
for(int i=1;i<n;i++){
int pos=i;
for(int j=i+1;j<=n;j++){
if(fabs(l[j][i])>fabs(l[pos][i]))
pos=j;
}
if(fabs(l[pos][i])<eps) return 0.0;
if(i!=pos) swap(l[i],l[pos]),ans*=-1;
for(int j=i+1;j<=n;j++){ // 消除l[j][i]
double t=l[j][i]/l[i][i];
for(int k=i;k<=n;k++){
l[j][k]=(l[j][k]-l[i][k]*t);
}
}
}
for(int i=1;i<=n;i++) ans*=l[i][i];
return ans;
}
};
Matrx_Tree T;
|
2. 有向图
对于求解内向树，把 \(D_{i,i}\) 改为 \(dout_i\) 。
对于求解外向树，把 \(D_{i,i}\) 改为 \(din_i\)
然后删去的一定是 \(root\) 行 \(root\) 列， （\(root\) 为内向树外向树的根）。