题解：
矩阵树定理入门题
一个图的邻接矩阵G：对于无向图的边(u,v)，G[u][v]++,G[v][u]++
一个图的度数矩阵D：对于无向图的边(u,v)，D[u][u]++,D[v][v]++;
而通过这两个矩阵就可以构造出图G的基尔霍夫矩阵：C=D-G.
Matrix Tree定理：将图G的基尔霍夫矩阵去掉第i行和第i列(i可以取任意值，可以证明所得到的结果相同)，得到(n-1)*(n-1)的矩阵
Part 2 Matrix Tree定理在有向图上的拓展
Matrix Tree定理的拓展与延伸------有向图的Matrix Tree定理
对于有向图G，不存在生成树的概念，但存在树形图的概念。
树形图：以i点为根节点的树形图有(n-1)条边，从i节点出发可以到达其他所有(n-1)个节点.
定义： 有向图的邻接矩阵G：对于有向图的边(u,v)，G[u][v]++.
有向图的度数矩阵D：对于有向图的边(u,v)，D[v][v]++.
尤其需要注意的是：有向图的度数矩阵指的是一个点的入度，而不是出度。
而有向图的基尔霍夫矩阵的构造方式是一模一样的：C=D-G.
有向图Matrix Tree定理：
将有向图G的基尔霍夫矩阵去掉第i行和第i列，得到(n-1)*(n-1)的矩阵，
对这个矩阵进行行列式的值求解，abs(det(A))就是以i为根的树形图的个数。
行列式相关结论：
行列式与它的转置行列式相等；
互换行列式的两行（列），行列式变号；
行列式的某一行（列）的所有的元素都乘以同一数k，等于用数k乘此行列式；
行列式如果有两行（列）元素成比例，则此行列式等于零；
若行列式的某一列（行）的元素都是两数之和，则这个行列式是对应两个行列式的和；
把行列式的某一列（行）的各元素乘以同一数然后加到另一列（行）对应的元素上去，行列式不变
在求解行列式时，我们利用高斯消元将其变为上三角矩阵，答案就是pai(a[i][i])
另外注意到高斯消元中有除法运算，但是这题中的模数并没有逆元，所以我们用辗转相除来减
另外注意到交换两行符号变号要记录一下
另外不是房间的点不要算
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rint register ll
const ll mo=1e9;
char ss[<<],*A=ss,*B=ss;
char gc()
{
return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
}
template<class T> void read(T &x)
{
rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=c^;
while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^);
}
ll n,m,s;
ll a[][],ff[][];
ll guass()
{
s--;
int cnt=;
for (ll i=;i<=s;i++)
{
/* ll now=i;
for (ll j=i+1;j<=s;j++)
if (abs(a[j][i])>abs(a[now][i])) now=j;
if (now!=i)
for (ll j=1;j<=s;j++) swap(a[i][j],a[now][j]); */
for (ll j=i+;j<=s;j++)
while (a[j][i])
{
ll kk=a[i][i]/a[j][i];
for (ll k=;k<=s;k++) a[i][k]=(a[i][k]-kk*a[j][k])%mo;
for (ll k=;k<=s;k++) swap(a[i][k],a[j][k]);
cnt++;
}
}
ll ans=; if (cnt%) ans=-;
for (ll i=;i<=s;i++)
ans=(ans*a[i][i])%mo;
return (ans+mo)%mo;
}
ll js(ll x,ll y)
{
return(ff[x][y]);
}
void cl(ll x1,ll y1,ll x2,ll y2)
{
ll k1=js(x1,y1),k2=js(x2,y2);
a[k1][k2]--; a[k2][k2]++;
}
char c[][];
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m;
for (ll i=;i<=n;i++) cin>>c[i];
int num=;
for (ll i=;i<=n;i++)
for (ll j=;j<=m;j++)
if (c[i][j-]=='.') ff[i][j]=++num;
for (ll i=;i<=n;i++)
for (ll j=;j<=m;j++)
{
if (i!=n)
if (c[i][j-]=='.'&&c[i+][j-]=='.')
cl(i,j,i+,j);
if (i!=)
if (c[i][j-]=='.'&&c[i-][j-]=='.')
cl(i,j,i-,j);
if (j!=m)
if (c[i][j-]=='.'&&c[i][j]=='.')
cl(i,j,i,j+);
if (j!=)
if (c[i][j-]=='.'&&c[i][j-]=='.')
cl(i,j,i,j-);
}
s=num;
/*for (int i=1;i<=s-1;i++)
{
cout<<endl;
for (int j=1;j<=s-1;j++)
cout<<a[i][j]<<" ";
}
cout<<endl;*/
cout<<guass();
/* for (int i=1;i<=s;i++)
{
cout<<endl;
for (int j=1;j<=s;j++)
cout<<a[i][j]<<" ";
}
cout<<endl;*/
return ;
}