矩阵树定理

行列式

定义

行列式是矩阵树定理的一个重要的前置知识。

行列式是一个 $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$ 来自求除数逆元，如果对于实数行列式则没有）。

[!success]- 示例代码——实数行列式

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$ 。一看就满足这个性质，所以我们可以得到一个不需要求逆元的版本。

[!success]- 示例代码——整数取模行列式

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$ 。

但是对于重边呢，其实完整的矩阵树定理是这样的：

[!node] 矩阵树定理对于一个无向图，每一个边有一个边权 $w_i$,

满足去掉一行一列之后的 Laplace矩阵 值为 $\sum_{T}\prod_{e\in T} w_{e}$

所以只要是求所有生成树权值乘积之和的问题，都可以转化为矩阵树定理，而生成树个数就是当 $w_i$ 都为 $1$ 时的特殊情况。

[!success]- 示例代码——整数取模

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;

[!success]- 示例代码——实数

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$ 为内向树外向树的根）。