### 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; }