Mondriaan’s Dream

题目链接：POJ 2411

题目大意

给你一个 $n\ast m$ 的矩阵，然后你有 $1\ast 2$ 的木块。
然后问你有多少种方案可以填满整个矩阵。

思路

看到 $n,m⩽10$，考虑直接暴力状压。

设 $f_{i,j}$ 为当前搞完第 $i$ 列，突出的状态是 $j$ 的方案数。
那答案就是 $f_{n,0}$，接着考虑转移。

因为只要 $10$，所以可以直接暴力看两个状态之间是否能转移。
那能否转移呢？
对于是 $1$ 的位置，那它这个位置就不能放了，现在就是 $0$，所以就是 $S0\&S1=0$。
那对于是 $0$ 的位置，它可以竖着放变成 $1$，那这个无所谓。
如果横着放，那还是 $0$，而且这些部分必须两两的，所以就是 $S0|S1$ 的每一段 $0$ 的长度都是偶数。
然后这个偶数的这个预处理一下，就可以 $O(2^{n+n}n)$ 转移啦。

代码

#include<cstdio>
#include<cstring>
#define ll long long

using namespace std;

int n, m;
ll f[12][2048];//记得long long
bool ck[2048];

int main() {
	scanf("%d %d", &n, &m);
	while (n || m) {
		memset(ck, 0, sizeof(ck));
		for (int i = 0; i < (1 << m); i++) {
			ck[i] = 1;
			for (int j = 1; j <= m; j++) {
				if ((i >> (j - 1)) & 1) continue;//1直接跳过
				int cnt = 1;
				while (j < m && !((i >> j) & 1)) j++, cnt++;//统计0的数量
				if (cnt & 1) {ck[i] = 0; break;}//是奇数就不行，要都是偶数
			}
		}
		
		memset(f, 0, sizeof(f));
		f[0][0] = 1;//DP转移
		for (int i = 1; i <= n; i++) {
			for (int S = 0; S < (1 << m); S++) {
				if (!f[i - 1][S]) continue;
				for (int T = 0; T < (1 << m); T++) {
					if (!(S & T) && ck[S | T]) {//条件
						f[i][T] += f[i - 1][S];
					}
				}
			}
		}
		printf("%lld\n", f[n][0]);
		
		scanf("%d %d", &n, &m);
	}
	
	return 0;
}