这里简单讲一下矩阵树定理：
我们分 3 种情况：
1. 给定一个无向图，求生成树个数.
2. 给定一个有向图，求以一个点为根的内向树个数.
3. 给定一个有向图，求以一个点为根的外向树个数.
case1:
构造度数矩阵 $S1$，满足 $S1_{i,i}$ 等于 $i$ 点的度数（一条无向边当成两条有向边，且只有对角线有值）
构造邻接矩阵 $S2$，满足 $S2_{i,j}$ 等于 $(i,j)$ 之间边的个数（一条无向边当成两条有向边）
令矩阵 $d=S1-S2$，则生成树个数就等于 $d$ 去掉任意一行+一列后的行列式的值.
case2:
将 $1$ 中那个 $S1$ 矩阵中 $S1_{i,i}$ 变成 $i$ 点的出度.
然后去掉矩阵 $d$ 中根节点所在的行与列.
case3:
将 $1$ 中那个 $S1$ 矩阵中 $S1_{i,i}$ 变成 $i$ 点的入度.
然后去掉矩阵 $d$ 中根节点所在的行与列.
code:
#include <cstdio>
#include <algorithm>
#define N 300
#define mod 10007
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int a[N][N],n,m;
int qpow(int x,int y)
{
int tmp=1;
for(;y;y>>=1,x=(ll)x*x%mod)
if(y&1) tmp=(ll)tmp*x%mod;
return tmp;
}
int INV(int x) { return qpow(x,mod-2); }
int gauss()
{
int ans=1,i,j,k;
for(i=2;i<=n;++i)
{
k=i;
for(j=i+1;j<=n;++j) if(a[j][i]>a[k][i]) k=j;
if(k!=i) swap(a[i],a[k]),ans*=-1;
if(!a[i][i]) return 0;
int inv=INV(a[i][i]);
for(j=i+1;j<=n;++j)
{
int t=(ll)(inv*a[j][i]%mod+mod)%mod;
for(k=i;k<=n;++k) a[j][k]=(ll)(a[j][k]%mod-(ll)t*a[i][k]%mod+mod)%mod;
}
}
if(ans<0) ans+=mod;
for(i=2;i<=n;++i) ans=(ll)(ans*a[i][i]%mod+mod)%mod;
return ans;
}
int main()
{
// setIO("input");
int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
// y->x
--a[y][x];
++a[x][x];
}
printf("%d\n",gauss());
return 0;
}
BZOJ 5297: [Cqoi2018]社交网络 矩阵树定理
原文：https://www.cnblogs.com/guangheli/p/12256306.html