几个需要重点理解的地方
- 因为要把棋盘填满，所以对于每种方案，如果把能横放的位置放好，那么剩下的空位只能竖放，并且竖放只能这样放，是唯一确定的。因此我们只需要考虑横放应该要怎么放，总的摆放方案实际上就等于所有合法的横放方案。如果只考虑竖放也同理。这里我们默认只考虑横放，所以下面的代码都是基于只考虑横放进行的。
f[i][j]表示从第 i - 1 列伸出到第 i 列的方案为 j 的所有方案。前 i - 1 列有各种不同的摆法都可以使得最终从第 i - 1 列伸出到第 i 列的方案为 j，故f[i][j]就是这些方案的总和。- 对于方案 j，1表示第 i - 1 列伸出到第 i 列，0表示第 i - 1 列没有伸出到第 i 列，所以最终 j 会是一个二进制表示，它的每一位就代表某列上对应位置的方案。但注意，实际存储时，j 存的是一个十进制数，但我们利用的是它的二进制表示。这也是体现状态压缩的地方，许多不同的状态被压缩成用一个数来表示。
- 由于当横放放好后，空出来的位置是留给竖放的，所有并非所有横放方案都合法，我们要把不合法的剔除。不合法的方案有下：
- 对于某一列的某个方案 j，如果出现了连续的奇数个0，那么该方案不合法。因为剩下的空位要留给1 * 2的小方块竖放，所以奇数个空位一定有一个放不下。
- 对于从第 i - 1 列伸出到第 i 列的方案 j 和从第 i - 2 列伸出到第 i - 1 列的方案 k ，他们共同决定了第 i - 1 列上的摆放是否合法。如果他们在某个位置同时横放，那么就会重合，则不合法。如果他们合并在第 i - 1列上会出现连续的奇数个0，那么也不合法（这种情况实际上就是合并列引入的目的，详见下方参考题解中对于
(j & k) == 0和st[j | k]处的解释，这就是合并列的实质）。 - 对于以上两种情况，总结下来就是对于某个方案，首先自身要合法（自己没有连续奇数个0），然后与相邻方案合并后要合法（合并后不重合，且不会出现连续奇数个0）。
f[0][0] = 1表示从第 -1 列伸出到第 0 列，方案为 0 的所有方案有 1 种，这其实是一种假想情况，因为不存在第-1列，也就是第0列的方案只能是00…0，也就是0。- 最后输出的
f[m][0]表示当从第 m - 1 列伸出到第 m 列的方案为 0，此时整个棋盘摆满。直观上就是第 m - 1列没有捅出到棋盘外面，因为实际一共只有m - 1列（从0开始）。
未优化写法
#include <iostream>
#include <cstring>
using namespace std;
//棋盘最大为N * N，最多会有2 ^ N（即1 << N）种方案（每个格子都是选或不选两种方案）
const int N = 12, M = 1 << N;
int n, m;
//f[i][j]表示从第 i - 1 列伸出到第 i 列的方案为 j 的所有方案
//前 i - 1 列有各种不同的摆法都可以使得最终从第 i - 1 列伸出到第 i 列的方案为 j，故f[i][j]就是这些方案的总和
//对于方案j，1表示第 i - 1 列伸出到第 i 列，0表示第 i - 1 列没有伸出到第 i 列
long long f[N][M];
//记录当前方案是否为 会出现连续的奇数个0 的非法方案
//因为我们全部横放，留出来的空位留给竖放，如果有连续奇数个0的情况，那么一定会有一格竖放放不下，这就是非法的方案
bool st[M];
int main()
{
//当n, m均不为0时继续输入
while(cin >> n >> m, n || m)
{
//预处理
//遍历所有方案，先把所有会出现连续的奇数个0的方案剔除（自己要合法）
for(int i = 0; i < 1 << n; i++)
{
st[i] = true; //初始默认该方案合法
int cnt = 0; //记录当前连续出现的0的个数
//逐行遍历每个位置，记录连续出现的0的个数
for(int j = 0; j < n; j++)
{
//如果当前位置为1，说明上一组连续出现的0在此截止
//从这里可以看出，我们实际是在该列从下往上找连续0的
if(i >> j & 1)
{
//特判：如果上一组连续0的个数为奇数，那么该方案不合法
if(cnt & 1) st[i] = false;
//将cnt重置为0，继续累计下一组连续0的个数
cnt = 0;
}
//否则说明当前位置为0，计数+1
else cnt++;
}
//特判最后一组连续0是否为奇数个
//因为前面的代码只有在出现1时才截止统计上一组0，所以最后剩下的连续0需要在此额外判断
if(cnt & 1) st[i] = false;
}
//开始dp
//每一次询问初始化f，清除上一次询问的记录
memset(f, 0, sizeof f);
//从第-1列伸出到第0列，方案为0的所有方案有1种
//这其实是一种假想情况，因为不存在第-1列，也就是第0列的方案只能是00...0
f[0][0] = 1;
//遍历每一列，找到该列合法的所有方案。第0列方案已确定，故从第1列开始
for(int i = 1; i <= m; i++)
//遍历从第 i - 1 列伸出到第 i 列的方案j
for(int j = 0; j < 1 << n; j++)
//遍历从第 i - 2 列伸出到第 i - 1 列的方案k（为了递推）
for(int k = 0; k < 1 << n; k++)
//如果j，k两个方案合并后不会在某个位置上重合，并且合并后不包含连续奇数个0，则转移（合并后要合法）
if((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];
//最后根据定义，当从第 m - 1 列伸出到第 m 列的方案为0时，整个棋盘摆满
//直观上就是第 m - 1列没有捅出到棋盘外面，因为实际一共只有m - 1列（从0开始）
cout << f[m][0] << endl;
}
return 0;
}
优化写法
优化思路就是提前预处理出所有合法方案，预处理时对于不合法方案直接跳出遍历以节省时间
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 12, M = 1 << N;
int n, m;
long long f[N][M];
bool st[M];
//这是一个第一维长度为M的动态二维数组，用于存放最终筛选出来的所有合法方案
//state[i][j]表示可实现方案 i 的所有合法方案 j
vector<int> state[M];
int main()
{
while(cin >> n >> m, n || m)
{
//预处理1
//出现连续奇数个0的方案不合法，要剔除（自己要合法）
for(int i = 0; i < 1 << n; i++)
{
bool is_valid = true; //初始默认合法
int cnt = 0;
for(int j = 0; j < n; j++)
{
if(i >> j & 1)
{
if(cnt & 1)
{
is_valid = false;
break; //方案不合法时直接跳出，后续没必要遍历
}
cnt = 0;
}
else cnt++;
}
if(cnt & 1) is_valid = false;
st[i] = is_valid;
}
//预处理2
//合并后不重合，且合并后不会出现连续奇数个0（合并后要合法）
for(int i = 0; i < 1 << n; i++)
{
//初始化state，清除上一次询问的记录
state[i].clear();
for(int j = 0; j < 1 << n; j++)
if((i & j) == 0 && st[i | j])
//方案 j 合法，将其记录
state[i].push_back(j);
}
//开始dp
//初始化f，清除上一次询问的记录
memset(f, 0, sizeof f);
f[0][0] = 1;
for(int i = 1; i <= m; i++)
for(int j = 0; j < 1 << n; j++)
//遍历可实现方案j的所有合法方案k
for(auto k : state[j])
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
return 0;
}
