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

由于长宽都比较小，采用棋盘式状态压缩DP解决，此类任务一般是在棋盘内填各种形状的块，然后求方案数。

核心思想是：总方案数等于合法横向摆放小矩形方案数之和。下面的图形中，绿色为横向填充，黄色为纵向填充，图1是合法的，图2则是非法的。

设状态矩阵为dp[i][j]，其中i表示第i列，j表示横跨第i-1列和第i列的横向小矩阵的行号的二进制表示，如：

同时，存在如下约束条件：

• j&k == 0（设i-1列的状态为k）
• 摆完第i列后，第i列中放置纵向小矩阵的连续空格数要为偶数个，因此j|k中不能存在连续奇数个空格，这个可以通过预处理获得

对于第二个约束条件，很多题解说的是考虑当第i列摆放完后，第i列中不能存在连续的奇数个空格，即j|k中不存在连续奇数个0，其中第i列中不能存在连续的奇数个空格其实是不对的，因为第i列中有些空格属于横向小矩阵的头，这些空格应该作为1来考虑

初始状态：dp[0][0]=1，状态转移公式：dp[i][j] = sum(dp[i-1][k])，其中0 <=k<= 1<<n（n为行数）

参考链接

代码如下：

//
// Created by jt on 2020/9/28.
// 蒙德里安的梦想：https://ac.nowcoder.com/acm/contest/1046/A
#include <iostream>
#include <cstring> // memset
using namespace std;

const int M = 12, N = 1 << M;
long long dp[M][N];
bool state[N]; // state[i]==true表示i中连续0的个数都为偶数

int main() {
    int m, n; // m为行数，n为列数
    while (cin >> m >> n, m && n) {
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < 1 << m; ++i) {
            state[i] = true; int cnt = 0;
            for (int j = 0; j < m; ++j) {
                // 注意&的优先级低于==
                if ((i >> j & 1) == 0) ++cnt;
                else {
                    if((cnt & 1) == 1) {state[i] = false; break; }
                    else cnt = 0;
                }
            }
            if ((cnt & 1) == 1) state[i] = false;
        }
        dp[0][0] = 1; // 初始状态
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 1 << m; ++j) {
                for (int k = 0; k < 1 << m; ++k) {
                    // 满足两个约束条件
                    if ((state[j|k]) && ((j & k) == 0))
                        dp[i][j] += dp[i-1][k];
                }
            }
        }
        cout << dp[n][0] << endl; // 结果为第m+1列没有伸出小矩阵的情况
    }
}