BZOJ 1435. [ZJOI2009]多米諾骨牌

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