棋盘覆盖问题，用状态压缩的递推来做，一行的填充状态用二进制数s表示，以f[i][s]表示前i-1行全部填满，第i行状态是s的方案数，则：
f[0][1\dots 11]=1
f[i][s_0]=\Sigma f[i-1][s_k] (若1\dots 1\\s_k\\0\dots 0能通过一种填充方式转变成1\dots 1\\1\dots 1\\s_k)。
　　s_0与s_k之间的可行转换可以通过DFS全部求出来——在两个空行上随意填充，则s_0就是上面的一行取反，s_k就是下面一行：
101100101 ——~s_0
110011101 ——一个可行的s_k
　　填充方式有9种：

1   11   10   11   11   11   00   01   0
1,  11,  11,  10,  00,  01,  11,  11,  0

　　DFS方案可以预处理出来，但本题空间限制有点~!@#$%，所以就不保存了。
　　调试了一下发现不太对劲，因为填充方式并没有9种之多。

11   11
11,  00

这两个不能算作填充方式。\dots 00\dots\\ \dots 00\dots->\dots 11\dots\\ \dots 11\dots跟\dots 11\dots\\ \dots 00\dots->\dots 11\dots\\ \dots 11\dots是重复的。而\dots 00\dots\\ \dots 00\dots->\dots 11\dots\\ \dots 00\dots跟\dots 11\dots\\ \dots 00\dots就是重复的。
　　f要用到long long。
　　这个题在周伟的《状态压缩》中有非常详细的讲解，但我只能提供一个半成品（因为我没有成品）。
　　Submit 1: WA on 2。我傻……我把棋盘看成n*n的了……
　　Submit 2: WA on 6。我跟天皇的程序对拍了每一种情况，结果一致。然而天皇的程序AC，我的WA。我直接打表输出天皇程序计算的结果，还是WA on test 6。是不是long long的输出上有问题啊？
　　Submit x: AC。果然，改用iostream输出就一点事儿没有了。

?[Copy to clipboard]View Code CPP
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
48

#include <iostream>
using namespace std;
 
const int bin[10]={0,1,3,7,15,31,63,127,255,511};
long long f[2][512];
int n,m,k;
 
void dfs(int p,int ul,int ll,int ub,int lb)
{
    if (p>m)
    {
        if (!ub && !lb) f[k][ll]+=f[!k][(~ul)&bin[m]];
        return;
    }
    if (!ub && !lb)
    {
        dfs(p+1,ul<<1|1,ll<<1|1,0,0);
        //dfs(p+1,ul<<1|1,ll<<1|1,1,1);
        dfs(p+1,ul<<1|1,ll<<1|1,0,1);
        dfs(p+1,ul<<1|1,ll<<1|1,1,0);
    }
    if (!ub)
    {
        //dfs(p+1,ul<<1|1,ll<<1|lb,1,0);
        dfs(p+1,ul<<1|1,ll<<1|lb,1,1);
    }
    if (!lb)
    {
        dfs(p+1,ul<<1|ub,ll<<1|1,0,1);
        dfs(p+1,ul<<1|ub,ll<<1|1,1,1);
    }
    dfs(p+1,ul<<1|ub,ll<<1|lb,0,0);
    return;
}
 
int main()
{
    cin>>n>>m;
    if (m<n) swap(n,m);
    f[0][bin[m]]=1; k=1;
    for (int i=1;i<=n;++i,k^=1)
    {
        memset(f[k],0,sizeof(f[k]));
        dfs(1,0,0,0,0);
    }
    cout<<f[n&1][bin[m]];
    return 0;
}