「BZOJ4031」[HEOI2015]小Z的房间

Description

你突然有了一个大房子,房子里面有一些房间。事实上,你的房子可以看做是一个包含n×mn\times m个格子的格状矩形,每个格子是一个房间或者是一个柱子。在一开始的时候,相邻的格子之间都有墙隔着。

你想要打通一些相邻房间的墙,使得所有房间能够互相到达。在此过程中,你不能把房子给打穿,或者打通柱子(以及柱子旁边的墙)。同时,你不希望在房子中有小偷的时候会很难抓,所以你希望任意两个房间之间都只有一条通路。现在,你希望统计一共有多少种可行的方案。

Input

第一行两个数分别表示nnmm

接下来nn行,每行mm个字符,每个字符都会是.或者*,其中.代表房间,*代表柱子。

Output

一行一个整数,表示合法的方案数 (mod109)\pmod{10^9}

Sample Input

1
2
3
4
3 3
...
...
.*.

Sample Output

1
15

HINT

对于前100%100\%的数据,n,m9n,m\leq 9

Solution

矩阵树定理裸题。
无向图矩阵树定理:

  • 定义DD为图GG的度数矩阵,Di,i=iD_{i,i}=i点的度数,对于ij,Di,j=0i\neq j,D_{i,j}=0
  • 定义AA为图GG的邻接矩阵,Ai,j=1A_{i,j}=1iijj有边,对于i=j,Ai,j=0i=j,A_{i,j}=0

C[G]=D[G]A[G]C[G]=D[G]-A[G]
GG的生成树个数为det(C[G])\det(C[G])
行列式用高斯消元的方法做,不断做初等变换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

**#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 190;
struct Matrix {
ll a[N][N];
ll* operator [] (int x){return a[x];}
}D,A,C;
int n, m;
int tt[N][N];
int tot;
int id(int x, int y) {
if(!tt[x][y]) tt[x][y] = ++tot;
return tt[x][y];
}
int dx[] = {-1, 0};
int dy[] = {0, -1};
char s[N][N];
const ll p = 1e9;


void add(ll &x, ll v) {
x += v;
if(x >= p) x %= p;
}
ll solve() {
for(int i = 1; i <= tot; ++i)
for(int j = 1; j <= tot; ++j) C[i][j] = D[i][j] - A[i][j];
bool t = 0;
for(int i = 1; i <= tot; ++i) {
if(!C[i][i]) {
for(int j = i + 1; j <= tot; ++j) if(C[j][i]) {
for(int k = 1; k <= tot; ++k) swap(C[j][k], C[i][k]);
t ^= 1;
break;
}
}
for(int j = i +1; j <= tot; ++j) {
while(C[j][i]) {
ll tmp = C[j][i] / C[i][i];
for(int k = 1; k <= tot; ++k)
add(C[j][k], p - C[i][k] * tmp % p);
if(C[j][i] == 0) break;
t ^= 1;
for(int k = 1; k<= tot; ++k) swap(C[j][k], C[i][k]);

}
}
}
ll ans = 1;
for(int i = 1; i <= tot; ++i)
ans = ans * C[i][i] % p;
return t ? (p - ans) %p: ans;;
}
int main() {
n = read(), m = read();
for(int i = 1 ;i <= n; ++i)
scanf("%s", s[i] + 1);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) if(s[i][j] == '.'){
int x = id(i, j);
for(int k = 0; k <2; ++k) {
int r = i + dx[k];
int c = j + dy[k];
if(r < 1 || r > n || c < 1 || c > m || s[r][c] == '*') continue;
int y = id(r, c);
++D[x][x], ++D[y][y];
A[x][y] = A[y][x] = 1;
}
}
--tot;
writeln(solve());
return 0;
}