Problem

n 个点 m 条边的无向图，统计生成树个数。

Solution

前置技能

• 矩阵的含义，基本运算
• 行列式的含义，拉普拉斯展开

如何计算行列式

• 以拉普拉斯展开式进行暴力递归计算
• 将行列式转化为等价上三角行列式，计算 $\prod ^n _{i=1} a_{ii}$

Matrix-Tree 定理

适用于不含重边的情况。
构造矩阵 $\mathbf{D}$, 则
$$d_{ij}=\left\{\begin{matrix} d_i\ (i=j)\\ -1 \ (i\neq j,\ (i,j)\in E)\\ 0 \end{matrix}\right.$$

$d_i$ 为点 i 的度数。
矩阵 $\mathbf{D}$ 的任意余子式的绝对值为该图的生成树个数。
一般选择 $d_{nn}$ 的余子式计算。

n 阶矩阵的余子式就是 n 阶矩阵的 n - 1 阶主子式的行列式。

建议在了解前置技能的情况下观看文章（里面详细阐述了矩阵树定理的使用和行列式的求法）：http://www.cnblogs.com/finder-iot/p/8662187.html 。建议前置技能通过结合维基百科和教材了解。

上面文章的求行列式的代码个人认为是个很好的模板。只是理解起来可能不是特别轻松，但其实还是好懂的。

例题 -BZOJ4301 小 Z 的房间

模板题。
WA 了一发，多加几个取模之后就好了。

// Code by ajcxsu
// Problem: room

#include<bits/stdc++.h>
#define MOD (1000000000ll)
using namespace std;
typedef long long ll;

const int N=100;
ll D[N][N]; // 矩阵
bool mp[N][N];
int idx[N][N], id;


int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    char ch;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) {
            cin>>ch;
            if(ch=='.') mp[i][j]=1, idx[i][j]=id++;
        }
    int mv[]={0,1,0,-1,0};
    for(int i=0,ii,jj,u,v;i<n;i++)
        for(int j=0;j<m;j++) {
            if(!mp[i][j]) continue;
            for(int k=1;k<=4;k++) {
                ii=i+mv[k-1], jj=j+mv[k];
                if(ii>=0 && ii<n && jj>=0 && jj<m && mp[ii][jj]) {
                    u=idx[i][j], v=idx[ii][jj];
                    D[u][u]++;
                    D[u][v]=-1;
                }
            }
        }
    ll ans=1;
    for(int i=0;i<id-1;i++) for(int j=0;j<id-1;j++) D[i][j]%=MOD;
    for(int i=0;i<id-1;i++) {
        for(int j=i+1;j<id-1;j++) {
            while(D[j][i]) {
                ll tmp=D[i][i]/D[j][i];
                for(int k=0;k<id-1;k++) D[i][k]=((D[i][k]-D[j][k]*tmp)%MOD +MOD) % MOD;
                swap(D[i],D[j]), ans=-ans;
            } // 这个while很有灵性，因为是整数除，这样保证至少一行的i列元会被消为0.
        }
        ans=((ans*D[i][i])%MOD +MOD) % MOD;
        if(ans==0) break;
    }
    cout<<ans<<endl;
    return 0;
}