来自《算法竞赛进阶指南》。做点笔记。

状态压缩 DP。考虑用一个 $M$ 位二进制数，其中 $1$ 表示这一列是一个竖着的 1*2 长方形的上半部分，$0$ 表示其他情况。

转移限制：

1. j 和 k 执行按位与运算的结果是 $0$。保证 $1$ 下方是 $0$。
2. j 和 k 执行按位或运算的结果中每一段连续 $0$ 都必须是偶数个，因为横着放的 1*2 长方形宽度必然是偶数。

$O(4^M N)$

#include <iostream>
using namespace std;
int n, m;
long long f[12][1<<11];
bool in_s[1<<11];
int main()
{
	while (cin >> n >> m && n) {
		for (int i = 0; i < 1<<m; i++) {
			in_s[i] = 1;
			bool hasodd = 0, cnt = 0;
			for (int j = 0; j < m; j++) {
				if (i&(1<<j)) hasodd |= cnt, cnt = 0;
				else cnt ^= 1; 
			}
			in_s[i] = hasodd|cnt ? 0 : 1;
		}
		f[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < 1<<m; j++) {
				f[i][j] = 0;
				for (int k = 0; k < 1<<m; k++) {
					if (in_s[j|k] && (j&k)==0) {
						f[i][j] += f[i-1][k];
					}
				}
			}
		}
		cout << f[n][0] << endl;
	}
	return 0;
}