题目概述

有 $n\times m$ 的网格，每个网格是房间或者柱子，周围都有墙，问打破墙使得房间连成一棵树的方案数。

解题报告

矩阵树裸题，问题是行列式取模，因为不是质数所以不能逆元。

那么辗转相除就行啦……注意每次交换行列式都需要变号。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=9,maxm=9,maxt=maxn*maxm,MOD=1e9;

int n,m,ID[maxn+5][maxn+5],a[maxt+5][maxt+5];char s[maxn+5][maxm+5];

inline void AMOD(int &x,int y) {if ((x+=y)>=MOD) x-=MOD;}
inline int Det(int n,int ans=1){
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) a[i][j]=(a[i][j]+MOD)%MOD;
    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j++)
            if (a[i][j]) {if (j>i) {for (int k=i;k<=n;k++) swap(a[i][k],a[j][k]);ans=-ans;}break;}
        for (int j=i+1;j<=n;j++)
            while (a[j][i]){
                int t=a[j][i]/a[i][i];for (int k=i;k<=n;k++) AMOD(a[j][k],MOD-(LL)a[i][k]*t%MOD);
                if (!a[j][i]) break;for (int k=i;k<=n;k++) swap(a[i][k],a[j][k]);ans=-ans;
            }
    }for (int i=1;i<=n;i++) ans=(LL)ans*a[i][i]%MOD;ans=(ans+MOD)%MOD;return ans;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
    for (int i=1;i<=n;i++)
        for (int j=1,x,y;j<=m;j++)
            if (s[i][j]=='.'){
                x=ID[i][j]=++ID[0][0];
                if (i>1&&(y=ID[i-1][j])) a[x][x]++,a[y][y]++,a[x][y]--,a[y][x]--;
                if (j>1&&(y=ID[i][j-1])) a[x][x]++,a[y][y]++,a[x][y]--,a[y][x]--;
            }
    return printf("%d\n",Det(ID[0][0]-1)),0;
}