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