状态压缩DP：蒙德里安的梦想

Dp	状态表示 f(i,j) 化零心的为整体的 “化零为整”	集合	前i-1列已经摆好，且从第i-1列伸出到第i列的状态是j行的所有方案，j使用十进制表示二进制
		属性
	状态计算 （划分） 化整体的为零星的 “化整为零”	划分	先放横着的，再放竖着的 看枚举最后一步哪些行是放了1*2的方格， 假设用k表示最后  从第i-1列伸出到第i列的状态是k，那j能作为一种方案的条件是(j&k)==0, 第二个就是说前i-1列空着的小方块必须要能被竖着的小方块塞满，那么意味着第i-1列连续空着的位置长度必须是偶数。最后的答案为f(m,0)

 所有方案数量等于拜访横着的方格的所有方案数量

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;typedef long long LL;const int N = 12, M = 1 << N;int n, m;
LL f[N][M];
vector<int> state[M];
bool st[M];int main()
{while (cin >> n >> m, n || m){for (int i = 0; i < 1 << n; i ++ ){int cnt = 0;bool is_valid = true;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;}for (int i = 0; i < 1 << n; i ++ ){state[i].clear();for (int j = 0; j < 1 << n; j ++ )if ((i & j) == 0 && st[i | j])state[i].push_back(j);}memset(f, 0, sizeof f);f[0][0] = 1;for (int i = 1; i <= m; i ++ )for (int j = 0; j < 1 << n; j ++ )for (auto k : state[j])f[i][j] += f[i - 1][k];cout << f[m][0] << endl;}return 0;
}