矩阵树定理

luckydrawbox · 2023-10-16 13:19:45 · 个人记录

其实也可以叫做行列式的板子。

• 将无向图的 \text{Kirchhoff} 矩阵同时去掉任意一行一列，剩下的矩阵的行列式绝对值，就是这个无向图的生成树个数，带权则为积。
• 将有向图的 \text{Kirchhoff} 矩阵同时去掉根所在一行一列，剩下的矩阵的行列式绝对值，就是这个有向图的生成树个数，带权则为积。
• 如果是有向图的外向树，则度数矩阵应为 d_{i,i}=\sum_{j=1}^na_{j,i}，即入边之和。
• 如果是有向图的内向树，则度数矩阵应为 d_{i,i}=\sum_{j=1}^na_{i,j}，即出边之和。
• 如果是无向图，则度数矩阵应为 d_{i,i}=\sum_{j=1}^na_{i,j}+a_{j,i}，即无向边之和。
• 将度数矩阵减去边矩阵，就得到了 \text{Kirchhoff} 矩阵。

变量

函数

代码

struct Matrix_Tree{
    ll *a[N],b[N][N];
    void init(int n){
        for(int i=1;i<=n;i++)a[i]=b[i];
        memset(b,0,sizeof(b));
    }
    ll det(int n){
        ll ans=1,f=1;
        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]),f*=-1;
                    break;
                }
            if(a[j][j]==0)return 0;
            ans=ans*a[j][j]%mod;
            ll t=qmi(a[j][j],mod-2);
            for(int k=j;k<n;k++)a[j][k]=a[j][k]*t%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)%mod;
            }
        }
        return (ans*f+mod)%mod;
    }
}tree;