传送门
emm在雅礼集训的时候听到的一道题 上来就觉得是插头dp 最后果然是轮廓线状压233
我们简化一下题意。 有一个n*m的网格，每个格子是空地或障碍物，询问把每一个空地看成障碍物的情况下，用1*2的骨牌覆盖（可以留有空地）的方案数 对1e9+7取模 bzoj和洛咕题面都挂了233
我们发现留有空地就很烦，所以我们可以把空地看成1*1的骨牌，这样的话我们统计的方案数就是用1*1的骨牌和1*2的骨牌完全覆盖网格的方案数。
骨牌覆盖！ ——》轮廓线状压！
但是我们发现如果对于每个格子直接计算的话 时间复杂度是O(n^3*2^m) 根本无法承受
所以我们考虑另一种做法 我们可以选择对前后缀进行合并这样的话复杂度就降到了O(n^2*2^m)
我们考虑如何对前后缀进行合并 即什么样的两条轮廓线是合法的
对应红色的格子作为我们的合并的格子的话 首先要求它上下两个格子已经被覆盖过了 然后就是上下对应的蓝绿格子应该状态相同 这样才能竖着填满棋盘（我们现在只考虑竖着因为横向的覆盖是在轮廓线dp的时候已经讨论过了）
所以我们对前后分别进行一次轮廓线dp（讨论横着放1*2竖着放1*2放1*1和不放） 然后最后统计答案的时候进行合并即可
附代码。（哦对bzoj卡空间只能开到1<<17不过也够了233）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 20021225
#define ll long long
#define mdn 1000000007
using namespace std;
int f[18][18][1<<17],g[18][18][1<<17];
int bit[18],n,m,top;
int mp[18][18];
void add(int &x,int y){x=(x+y)%mdn;}
void work()
{
//int top=(1<<m)-1;
f[1][1][top]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int x=i,y=j+1;
if(j==m) x=i+1,y=1;
if(x>n) continue;
for(int st=0;st<=top;st++)
if(f[i][j][st])
{
int tmp=f[i][j][st];
if((st&bit[j])==0&&mp[i][j]) continue;
if((st&bit[j])==0)
{
add(f[x][y][st|bit[j]],tmp);
continue;
}
if(mp[i][j]) add(f[x][y][st],tmp);
else
{
add(f[x][y][st],tmp);
add(f[x][y][st^bit[j]],tmp);
if(j>1&&(st&bit[j-1])==0) add(f[x][y][st|bit[j-1]],tmp);
}
}
}
g[n][m][top]=1;
for(int i=n;i;i--)
for(int j=m;j;j--)
{
int x=i,y=j-1;
if(j==1) x=i-1,y=m;
if(x<1) continue;
for(int st=0;st<=top;st++)
if(g[i][j][st])
{
int tmp=g[i][j][st];
if((st&bit[j])==0&&mp[i][j]) continue;
//printf("%d %d %d %d
",i,j,st,g[i][j][st]);
if((st&bit[j])==0)
{
add(g[x][y][st|bit[j]],tmp);
continue;
}
if(mp[i][j]) add(g[x][y][st],tmp);
else
{
add(g[x][y][st],tmp);
add(g[x][y][st^bit[j]],tmp);
if(j<m&&(st&bit[j+1])==0) add(g[x][y][st|bit[j+1]],tmp);
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
bit[1]=1;top=(1<<m)-1;
for(int i=2;i<=m;i++) bit[i]=bit[i-1]<<1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&mp[i][j]);
work();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j])
{
printf("0 ");
continue;
}
int ans=0;
for(int s=0;s<=top;s++)
{
if(s&bit[j])
add(ans,(ll)f[i][j][s]*g[i][j][s]%mdn);
//printf("%d %d %d %d
",i,j,f[i][j][s],g[i][j][s]);
}
printf("%d ",ans);
}
printf("
");
}
return 0;
}