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

Posted by xiaodao
Category: BZOJ
Tags: 容斥原理