题目概述

有 $n\times m$ 的客厅，要用 $L$ 型地板覆盖整个客厅，求方案数。

解题报告

棋盘覆盖问题，$min\{n,m\}\le 10$ ，想到插头DP，由于每个 $L$ 型地板只有一个拐角，所以设计这样的状态：$0$ ：无插头。$1$ ：有插头，之前没有出现拐角。$2$ 有插头，之前出现过拐角。

大力分类讨论就行了，这里就不列举了，可以参考另外两道插头DP的讨论方法：BZOJ1814,HDU1693。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100,maxm=10,maxs=177147,HA=99971,MOD=20110520;

int n,m;char pic[maxn+5][maxm+5];
struct Hashmap{
    int E,lnk[HA],son[maxs+5],nxt[maxs+5],w[maxs+5];
    inline void Clear() {for (int i=0;i<HA;i++) lnk[i]=0;E=0;}
    inline void Add(int x,int y) {son[++E]=y;w[E]=0;nxt[E]=lnk[x];lnk[x]=E;}
    inline int& operator [] (const int &x){
        for (int j=lnk[x%HA];j;j=nxt[j]) if (son[j]==x) return w[j];
        Add(x%HA,x);return w[E];
    }
}f[2];

inline char getpic() {char ch=getchar();while (ch!='*'&&ch!='_') ch=getchar();return ch;}
#define pos(s,i) ((s)>>((i)<<1)&3)
#define val(i,j) ((j)<<((i)<<1))
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);
    if (n<m) {swap(n,m);for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) pic[j][i]=getpic();}
    else for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) pic[i][j]=getpic();f[0][0]=1;
    for (int i=1,c=1;i<=n;i++){
        int F;f[c].Clear();for (int e=1;e<=f[c^1].E;e++) if (F=f[c^1].w[e]) f[c][f[c^1].son[e]<<2]=F;
        for (int j=(f[c^1]=f[c],1);j<=m;j++,c^=1){
            for (int e=(f[c].Clear(),1);e<=f[c^1].E;e++){
                int s=f[c^1].son[e];F=f[c^1].w[e];if (!F) continue;int A=pos(s,j-1),B=pos(s,j);
                if (pic[i][j]=='*') {if (!A&&!B) AMOD(f[c][s],F);}
                else if (!A&&!B){
                    if (pic[i][j+1]=='_') AMOD(f[c][s^val(j,1)],F);
                    if (pic[i+1][j]=='_') AMOD(f[c][s^val(j-1,1)],F);
                    if (pic[i][j+1]=='_'&&pic[i+1][j]=='_') AMOD(f[c][s^val(j-1,2)^val(j,2)],F);
                } else if (!A&&B==1){
                    if (pic[i][j+1]=='_') AMOD(f[c][s^val(j,1)^val(j,2)],F);
                    if (pic[i+1][j]=='_') AMOD(f[c][s^val(j,1)^val(j-1,1)],F);
                } else if (!A&&B==2){
                    AMOD(f[c][s^val(j,2)],F);
                    if (pic[i+1][j]=='_') AMOD(f[c][s^val(j,2)^val(j-1,2)],F);
                } else if (A==1&&!B){
                    if (pic[i][j+1]=='_') AMOD(f[c][s^val(j-1,1)^val(j,1)],F);
                    if (pic[i+1][j]=='_') AMOD(f[c][s^val(j-1,1)^val(j-1,2)],F);
                } else if (A==1&&B==1) AMOD(f[c][s^val(j-1,1)^val(j,1)],F);
                else if (A==1&&B==2) /*Impossible*/;
                else if (A==2&&!B){
                    AMOD(f[c][s^val(j-1,2)],F);
                    if (pic[i][j+1]=='_') AMOD(f[c][s^val(j-1,2)^val(j,2)],F);
                } else if (A==2&&B==1) /*Impossible*/;
                else if (A==2&&B==2) /*Impossible*/;
            }
        }
    }printf("%d\n",f[n*m&1][0]);return 0;
}