题解 P2595 【[ZJOI2009]多米诺骨牌】

· · 题解

这道题还是比较好想的，就是细节多了一些。

网上的题解大部分都是插头DP，我来写一份状压+容斥的题解。

首先考虑没有限制的情况，即，用1*2的骨牌覆盖整个网格图，有多少种不同的方案？

考虑按照

(1,1),(1,2),...,(1,m),(2,1),...,(2,m),...,(n,1),...,(n,m)

的顺序加点。加入(i,j)时统计用骨牌覆盖(i-1,j)(i,j)和覆盖(i,j-1)(i,j)的方案数，以及不覆盖(i,j)的方案数。我们需要知道(i-1,j)和(i,j-1)的信息。

但是(i-1,j+1),...,(i-1,m),(i,1),...,(i,j-2)之后还可能和某个(i,j)一上一下地用骨牌覆盖，所以也要记下来。用一个状压维护。

更进一步，我们考虑对所有网格图的所有子矩阵求出没有限制的答案（之后有用）。设左上角为(x_1,y_1)，右下角为(x_2,y_2)的矩阵的答案是dp[y_1][x_1][y_2][x_2]。（行列颠倒后转移会更简便。）在求解dp[y_1][x_1][y_2][n]的过程中，我们一定有某个时刻记录了(k,y_1),(k,y_1+1),...,(k,y_2)的状态。将所有状态的DP值加起来就是dp[y_1][x_1][y_2][k]。所以只要枚举y_1,x_1,y_2求解即可。

现在考虑有限制的情况。想到容斥。比较流行的容斥有两种：

$(2)$代表元容斥。即，为了求出让条件$1,2,...,n$均满足的情况数，我们可以枚举不满足的条件中编号最小的那一个。 都用子集容斥显然不行。因为复杂度是$2^{n+m}$。都用代表元容斥也不行。因为枚举了第一个没有横跨的行后，求的实际上是分割线上边和下边均有列横跨的方案数。而我们要求的是分割线上边和下边至少有一个有列横跨的方案数。 所以对列用容斥，行用代表元。枚举哪些列的夹缝没有横跨，它们将矩阵分为若干块。记$f_i$表示前$i$行的矩阵合法的方案数。$g[i][j]$表示$i$行到$j$行任意摆放且不横跨夹缝的方案数。则有： $g[i][j]=\prod_{x=1}^k dp[l_x][i][r_x][j]

其中l_t表示第t块的左端点。r_t亦然。

f[i]=g[1][i]-\sum_{j=2}^{i}f[j-1]*g[j][i]

这样，求出每个子集的f_n，子集容斥即可。

时间复杂度方面，一开始的预处理主要瓶颈在状压。它是指数级别的。最坏情况下是2^m。有n次会取到。每次要枚举n*n个点。时间复杂度O(2^m*n^3)。至于其他不能取到最坏复杂度的情况，由于复杂度不同级，可以略去。

后面的统计，子集容斥一次O(2^m)，代表元容斥一次O(n)，故时间复杂度为O(2^m*n)

总时间复杂度是O(2^m*n^3)。

很多人说我题解写得太详细是在浪费时间。用某学姐的话说，“好像在谈恋爱”。但我想，题解不仅是个人的总结，更是对其他人的帮助。这道题网络上有很多题解，但大多数都是三言两语就带过，很难看懂。不仅这道题，很多题也是一样。而我所做的，就是将我的理解，通过通俗易懂的方式，呈现给大家。能用短暂的两三年OI生涯，为更多OIer造福，我感到很欣慰。这就是所谓的“前人栽树，后人乘凉”。

代码：


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;

const int N=15;
const int T=1<<N;
const int mod=19901013;
int n,m,pre[N][N][N][N],tdp[2][T],ans;
int f[N],tl,cnt[T];
pair<int,int> lis[N];
char s[N][N];

namespace MATHEMATICS
{
    int add(int x,int y)
    {
        int ret=x+y;
        if(ret>=mod) ret-=mod;
        return ret;
    }
    int mi(int x,int y)
    {
        int ret=x-y;
        if(ret<0) ret+=mod;
        return ret;
    }

    void inc(int &x,int y)
    {
        x+=y;
        if(x>=mod) x-=mod;
    }
    void dec(int &x,int y)
    {
        x-=y;
        if(x<0) x+=mod;
    }

    int mul(int x,int y)
    {
        return 1LL*x*y%mod;
    }
}
using namespace MATHEMATICS;

void init()
{
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;++i) scanf("%s",&s[i]);
}

void cal(int xu,int yu,int xd)
{
    int i,j,S,mxS=1<<xd-xu+1;
    int oldpos=0,newpos=1;
    for(S=0;S<mxS;++S) tdp[0][S]=0;
    tdp[0][mxS-1]=1;

    for(i=yu;i<n;++i)
        for(j=xu;j<=xd;++j)
        {
            for(S=0;S<mxS;++S) tdp[newpos][S]=0;
            for(S=0;S<mxS;++S)
            {
                if(!tdp[oldpos][S]) continue;
                if(!(S&(1<<xd-xu))&&s[i][j]=='.'&&s[i-1][j]=='.')
                    inc(tdp[newpos][(S<<1)&(mxS-1)|1],tdp[oldpos][S]);
                if(!(S&1)&&s[i][j]=='.'&&j>xu&&s[i][j-1]=='.')
                    inc(tdp[newpos][(S<<1)&(mxS-1)|3],tdp[oldpos][S]);
                inc(tdp[newpos][(S<<1)&(mxS-1)],tdp[oldpos][S]);
            }
            if(j==xd)
            {
                for(S=0;S<mxS;++S)
                    inc(pre[xu][yu][xd][i],tdp[newpos][S]);
            }
            oldpos^=1,newpos^=1;
        }
}

void prework()
{
    int i,j,k;
    for(i=0;i<m;++i)
        for(j=0;j<n;++j)
            for(k=i;k<m;++k)
                cal(i,j,k);
}

int calc(int S)
{
    int i,j,k,las=0;tl=0;
    for(i=0;i<m-1;++i)
        if((1<<i)&S)
            lis[++tl]=make_pair(las,i),las=i+1;
    lis[++tl]=make_pair(las,m-1);

    for(i=0;i<n;++i)
    {
        f[i]=1;
        for(j=1;j<=tl;++j)
            f[i]=mul(f[i],pre[lis[j].first][0][lis[j].second][i]);
        for(k=0;k<i;++k)
        {
            int now=f[k];
            for(j=1;j<=tl;++j)
                now=mul(now,pre[lis[j].first][k+1][lis[j].second][i]);
            dec(f[i],now);
        }
    }

    return f[n-1];
}

void work()
{
    int ans=0,S,mxS=1<<m-1;
    for(S=0;S<mxS;++S) cnt[S]=cnt[S>>1]+(S&1);
    for(S=0;S<mxS;++S)
    {
        if(cnt[S]&1) dec(ans,calc(S));
        else inc(ans,calc(S));
    }
    printf("%d\n",ans);
}

int main()
{
    init();prework();work();
    return 0;
}