Luogu

BZOJ

分析

矩阵树定理板子题。

相邻的两个.间连一条边，然后直接算就行了。

注意模数是 $10^9$ 而不是 $10^9+7$ （我就这么 $\mathrm{WA}$ 了 $3$ 次，身败名裂）。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;
const int mod=1e9;

int n,m;
char s[N][N];
int id[N][N],tot;
int a[N][N];

inline int calc(int n) {
    int ans=1;
    for (re int i=1;i<=n;++i) {
        for (re int j=i+1;j<=n;++j)
            while (a[j][i]) {
                int t=a[i][i]/a[j][i];
                for (re int k=i;k<=n;++k) {
                    a[i][k]=(a[i][k]-1ll*a[j][k]*t%mod+mod)%mod;
                    swap(a[i][k],a[j][k]);
                }
                ans=mod-ans;
            }
        ans=1ll*ans*a[i][i]%mod;
    }
    return (ans+mod)%mod;
}

inline void add(int u,int v) {
    ++a[u][u],++a[v][v],--a[u][v],--a[v][u];
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) scanf("%s",s[i]+1);
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            if (s[i][j]=='.') id[i][j]=++tot;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j) {
            if (s[i][j]!='.') continue;
            if (id[i-1][j]) add(id[i-1][j],id[i][j]);
            if (id[i][j-1]) add(id[i][j-1],id[i][j]);
        }
    printf("%d\n",calc(tot-1));
    return 0;
}