LibreOJ 6301 「CodePlus 2018 3 月赛」白金元首与莫斯科

简单插头 DP 题。

骨牌覆盖，一张骨牌可以看做两个插头相接，即一条跨两格的线。
然后大力分类讨论即可。

这题要求枚举每个格子为障碍物的方案数，考虑正着反着各做一遍，然后统计相同状态之和。

代码：

#include <cstdio>
using namespace std;
const int N = 17;
const int mod = 1e9 + 7;
int n,m,full,a[N + 5][N + 5];
int f[N + 5][N + 5][(1 << N + 1) + 5],g[N + 5][N + 5][(1 << N + 1) + 5];
int ans[N + 5][N + 5];
inline void trans(int &s,int v)
{
    s = (s + v) % mod;
}
int main()
{
    scanf("%d%d",&n,&m),full = (1 << m + 1) - 1;
    for(register int i = 1;i <= n;++i)
        for(register int j = 1;j <= m;++j)
            scanf("%d",a[i] + j),a[i][j] ^= 1;
    f[0][m][0] = 1;
    for(register int i = 1;i <= n;++i)
    {
        for(register int j = 0;j < (1 << m);++j)
            f[i][0][j << 1] = f[i - 1][m][j];
        for(register int j = 1;j <= m;++j)
            for(register int s = 0;s <= full;++s)
                if(f[i][j - 1][s])
                {
                    int up = (s >> j) & 1,left = (s >> j - 1) & 1;
                    int v = f[i][j - 1][s];
                    if(!a[i][j])
                        !up && !left && (trans(f[i][j][s],v),1);
                    else if(!up && !left)
                        trans(f[i][j][s],v),
                        a[i + 1][j] && (trans(f[i][j][s + (1 << j - 1)],v),1),
                        a[i][j + 1] && (trans(f[i][j][s + (1 << j)],v),1);
                    else if(up && !left)
                        trans(f[i][j][s - (1 << j)],v);
                    else if(!up && left)
                        trans(f[i][j][s - (1 << j - 1)],v);
                }
    }
    g[n + 1][1][0] = 1;
    for(register int i = n;i;--i)
    {
        for(register int j = 0;j < (1 << m);++j)
            g[i][m + 1][j] = g[i + 1][1][j << 1];
        for(register int j = m;j;--j)
            for(register int s = 0;s <= full;++s)
                if(g[i][j + 1][s])
                {
                    int up = (s >> j - 1) & 1,left = (s >> j) & 1;
                    int v = g[i][j + 1][s];
                    if(!a[i][j])
                        !up && !left && (trans(g[i][j][s],v),1);
                    else if(!up && !left)
                        trans(g[i][j][s],v),
                        a[i][j - 1] && (trans(g[i][j][s + (1 << j - 1)],v),1),
                        a[i - 1][j] && (trans(g[i][j][s + (1 << j)],v),1);
                    else if(up && !left)
                        trans(g[i][j][s - (1 << j - 1)],v);
                    else if(!up && left)
                        trans(g[i][j][s - (1 << j)],v);
                }
    }
    for(register int i = 1;i <= n;++i)
        for(register int j = 1;j <= m;++j)
        {
            if(a[i][j])
                for(register int s = 0;s <= full;++s)
                    if(!(s & (1 << j - 1)) && !(s & (1 << j)))
                        ans[i][j] = (ans[i][j] + (long long)f[i][j - 1][s] * g[i][j + 1][s]) % mod;
            printf("%d%c",ans[i][j]," \n"[j == m]);
        }
}