Brief description:
给定一个 n×m 的矩形表格，其中有一些位置有障碍。现在要在这个表格内放一些 1×2 或者 2×1 的多米诺骨牌，使得任何两个多米诺骨牌没有重叠部分，任何一个骨牌不能放到障碍上。
并且满足任何相邻两行之间都有至少一个骨牌横跨，任何相邻两列之间也都至少有一个骨牌横跨。求有多少种不同的放置方法，注意你并不需要放满所有没有障碍的格子。
回忆多米诺骨牌完美覆盖。。显然我们可以轮廓线 DP。。
...
swap(p, q); f[p].clear();
ECH(it, f[q]){
d = it->se; int s = it->fi;
if(j && !_1(s, j) && _1(s, j-1)) f[p][s^_1(j-1)] += d; // 横着放
f[p][s^_1(j)] += d; // 竖着放或不放...
}
。。稍加修改可以支持障碍以及空隙。。。。
swap(p, q); f[p].clear();
ECH(it, f[q]){
d = it->se; int s = it->fi;
if (buf[i1][j] != '.'){
if (!_1(s, j)) f[p][s] += d; // 有障碍、必须不放
}
else{
if(j != j0 && !_1(s, j) && _1(s, j-1) && buf[i1][j-1] == '.') f[p][s^_1(j-1)] += d; // 横着放
if (!_1(s, j)){ // 是否没被覆盖
f[p][s] += d; // 不放
f[p][s^_1(j)] += d; // 竖着放
}
else{
f[p][s^_1(j)] += d; // 不放
}
}
}
。。。因此剩下只需要考虑 solid 的问题。。。
。方法一：加维。。复杂度太高。
。方法二：巧妙的容斥。。
const int N = 15;
int n, m; char buf[N][N+1];
map<int, Int> f[2]; Int d; int p, q;
Int ff[N+1][N+1][N+1][N+1], gg[N+1][N+1], g[N+1], z;
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif
RD(n, m); REP(i, n) RS(buf[i]);
REP(i0, n) REP(j0, m) FOR(j1, j0, m){
REP(i, 2) f[i].clear();
p = 0, q = 1; f[p][0] = 1;
FOR(i1, i0, n){
FOR_1(j, j0, j1){
swap(p, q); f[p].clear();
ECH(it, f[q]){
d = it->se; int s = it->fi;
if (buf[i1][j] != '.'){
if (!_1(s, j)) f[p][s] += d;
}
else{
if(j != j0 && !_1(s, j) && _1(s, j-1) && buf[i1][j-1] == '.') f[p][s^_1(j-1)] += d;
if (!_1(s, j)){
f[p][s] += d;
f[p][s^_1(j)] += d;
}
else{
f[p][s^_1(j)] += d;
}
}
}
}
ff[i0][i1][j0][j1] = f[p][0];
}
}
REP(s, _1(m-1)){
REP(i0, n) FOR(i1, i0, n){
gg[i0][i1] = 1; int p = -1, ss = s; ss |= _1(m-1);
while (ss){
int t = low_bit(ss);
ss ^= t; t = lg2(t);
gg[i0][i1] *= ff[i0][i1][p+1][t];
p = t;
}
}
REP_1(i, n){
g[i] = gg[0][i-1]; REP_1(j, i-1) g[i] -= g[j] * gg[j][i-1];
}
if (count_bits(s) & 1) z -= g[n];
else z += g[n];
}
cout << int(z) << endl;
}
