Zeratul's Blog

too naive=

一眼矩阵树=然后写完发现模数不太对=

然后发现直接搞好了=

/*
Matrix-Tree定理是解决生成树计数问题最有力的武器之一。
它首先于1847年被Kirchhoff证明。在介绍定理之前，我们首先明确几个概念：
1、G的度数矩阵D[G]是一个n*n的矩阵，并且满足：当i≠j时,dij=0；当i=j时，dij等于vi的度数。
2、G的邻接矩阵A[G]也是一个n*n的矩阵， 并且满足：如果vi、vj之间有边直接相连，则aij=1，否则为0。
我们定义G的Kirchhoff矩阵(也称为拉普拉斯算子)C[G]为C[G]=D[G]-A[G]，
则Matrix-Tree定理可以描述为：G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]
任何一个n-1阶主子式的行列式的绝对值。所谓n-1阶主子式，就是对于r(1≤r≤n)，
将C[G]的第r行、第r列同时去掉后得到的新矩阵，用Cr[G]表示
*/

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
using namespace std;
#define N 150
#define Z 5
#define ll long long
#define mo 1000000000
int xx[Z]={0,0,1,-1},yy[Z]={1,-1,0,0};
int n,m,id;
char c[N][N];
ll a[N][N],p[N][N];
inline int Find(int n){
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=(a[i][j]+mo)%mo;
    ll ans=1,f=1;
    for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			ll A=a[i][i],B=a[j][i];
            for(;B!=0;){
				ll t=A/B;A%=B;swap(A,B);
                for(int k=i;k<=n;k++)
                    a[i][k]=(a[i][k]-t*a[j][k]%mo+mo)%mo;
                for(int k=i;k<=n;k++)
                    swap(a[i][k],a[j][k]);
				f=-f;
			}
		}if(!a[i][i])return 0;
		ans=ans*a[i][i]%mo;
    }
	if(f==-1)return(mo-ans)%mo;return ans;
}
int main(){
	scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",c[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(c[i][j]=='.')p[i][j]=++id;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(c[i][j]=='.')
                for(int k=0;k<4;k++){
                    int x=i+xx[k],y=j+yy[k];
                    if(x<1||y<1||x>n||y>m||c[x][y]!='.')continue;
                    int u=p[i][j],v=p[x][y];
                    a[u][u]++;a[u][v]--;
                }
    printf("%d\n",Find(id-1));
}