291. 蒙德里安的梦想

1. 大致思路：当所有横向小方格 正确 摆放好后，竖向小方格就只有一种放法

2. 状态表示：

   f [ i, j ] 表示的集合是：摆放第 i 列，用 j 的二进制数 表示上一列横向摆放伸出来的小方格的情况（0 <= j <= 2 ^n - 1） （ 0 表示没有伸出来的，1 表示有）

   f [ i, j ] 表示的属性（值）是：这些情况的方案数

3. 状态计算：

   大致思路：枚举第 i - 1 列的所有状态

   用 j 表示第 i 列的突出小方格情况，用 k 表示第 i - 1 列的突出小方格的情况

   j 与 k 不能发生冲突，需要满足以下条件：
   1. ( j & k ) == 0;

   理解：从第 i - 1 列突到第 i 列的横向小方格所在的行不能与从第 i - 2 列凸到第 i - 1 列的横向小方格冲突，这就可以用位运算判断，当二者有凸出小方格的行相互交错时，二者相与就是0（都是0的话显然就是0）

4. (j | k) 这个新状态中不存在连续奇数个0

   理解：将 j 表示的状态与 k 表示的状态相叠加形成一个新的状态，这个新状态就是第 i - 1 列中被横向小方格所占的情况，若有连续的0，并且这些连续0的数量是奇数，这就不是 正确 的摆放，那这些剩下的空格子就不能被竖着的的小方块所填。

   在满足条件后，f [ i , j ] = ∑ f [ i - 1, k ] ( k 属于所有满足情况的方案的集合）

5. 时间复杂度：

   状态数量：11 * (2 ^ 11)

   状态转移：2 ^ 11

   大概在 10 ^ 7 左右

6. 结果分析：

   当状态转移计算完后，结果为 f [ m , 0 ]

   原因：
   f [ m, 0 ] 表示的含义是小方快可摆放区域的最后一列，没有方块凸到区域外

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 12, M = 1 << N;

typedef long long LL;

int n, m;
LL f[N][M];
// 存储(j | k)是否符合转移条件
bool st[M];

int main() {
    // 循环输入
    while (cin >> n >> m, n || m) {
        // 每次循环初始化一遍f
        memset(f, 0, sizeof f);

        // 预处理（j | k）所有可能状态，看状态中是否有连续奇数个0
        for (int i = 0; i < 1 << n; i ++ ) {
            // 假设当前状态满足情况
            st[i] = true;
            // cnt 表示当前段中连续 0 的个数
            int cnt = 0;
            // 从前往后枚举当前状态中的每一位二进制数
            for (int j = 0; j < n; j ++ )
                // 如果枚举到的二进制位上是1
                if (i >> j & 1) {
                    // 判断之前cnt是不是奇数
                    if (cnt & 1) st[i] = false;
                    // cnt 复位
                    cnt = 0;
                }
                else cnt ++ ;
            // 不要忘了最后检查一下cnt，可能有“1110”这种类似的情况
            if (cnt & 1) st[i] = false;
        }

        // DP
        // 初始化, 第 0 列的上一列不存在凸出的横向小方块
        f[0][0] = 1; 
        // 枚举每一列
        // 注意：小方格摆放的可行列是0 ~ m - 1
        for (int i = 1; i <= m; i ++ ) 
            // 枚举当前列的情况
            for (int j = 0; j < 1 << n; j ++ )
                // 枚举上一列的情况
                for (int k = 0; k < 1 << n; k ++ )
                    // 条件判断是否可以转移
                    if ((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];
        // 结果，表示小方块可摆放的最后一列（m - 1列）刚好摆好，没有凸出到m列的
        cout << f[m][0] << endl;
    }
    return 0;
}