矩阵树

题目描述

1331. 矩阵树

应用

求生成树个数

前置知识

Laplacian Matrix(拉普拉斯矩阵)

L=D-A,A是邻接矩阵,D是度矩阵

行列式计算

采用高斯消元法

逆元

(a/b)%mod = ((a%mod)*(c%mod))%mod
bc%mod=1

扩展欧几里得算法

int exgcd(int a,int b,int& x,int& y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int g=exgcd(b,a%b,x,y);
    int tmp=x;
    x=y;
    y=tmp-a/b*y;
    return g; 
}

快速幂

若gcd(a,pow)==1,$a^{pow-1}$和1同余,即a的逆元为$a^{m-2}$

int qpow(int a,int m){
    if(m==1) return a;
    int ans=1;
    if(m%2==1) ans=a;
    int q = qpow(a,m/2);
    return ((q*q)%pow*ans)%pow;
}

解题思路

• 求L矩阵
• 高斯消元,上三角行列式对角线元素为取余后的结果
• 对角线元素相乘