概述

轮廓线是已决策方格和未决策方格的分界线
轮廓线
我们逐格递推,到达当前这一格对应轮廓线如图,表示为一个m位二进制整数$k_0k_1k_2k_3k_4$
GF作为$k_5$,不作为dp状态,而视为判断dp是否为一个可行方案的条件。

题目

uva11270

骨牌覆盖,在状压dp中讲过一种做法
我们来研究怎么转移(当前状态为k):

  • 不放:上边一格必须填满,即 k0=1 ,直接k<<1
  • 竖放:上边一格必须为空,且不为第一行 k0=0, (k<<1)^(1<<m)^1
  • 横放:左边一格必须为空,且不为第一列 k5=0, (k<<1)^3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
int n,m,t;
LL d[2][1<<10];

inline void update(int a,int b)
{
if(b&(1<<m)) d[t][b^(1<<m)] += d[t^1][a];
}

int main()
{
//freopen("test.txt","r",stdin);
while(scanf("%d%d",&n,&m)==2)
{
if(n*m &1) puts("0");
else
{
if(n<m) swap(n,m);
memset(d,0,sizeof d);
d[0][(1<<m)-1] = 1;
t = 0;
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
t^=1;
memset(d[t],0,sizeof d[t]);
for(int k=0;k<(1<<m);++k)
{
update(k,k<<1); //不放
if(i && !(k&(1<<(m-1))))
update(k,(k<<1)^(1<<m)^1); //竖放
if(j && !(k&1)) update(k,(k<<1)^3); //横放
}
}
}
printf("%lld\n",d[t][(1<<m)-1]);
}
}
return 0;
}