重点在于下面这行代码

if (!(j & k) && st[j | k])

对于这行代码的理解（结合图解更佳）：

• 首先我们只需要考虑所有合法的横向放置的方案数

• 然后弄懂f[i][j]的含义：第i列所有从i-1列伸过来的长方形构成的状态的二进制表示

• 易知，伸到i-1列的长方形所在行不可能给第i列伸长方形，所以 (k & j == 0)

• 同时，第i列的不同状态j会影响到第i-1列总共放了那些格子，因为第i列的j是从第i-1列伸过来的（也就是说只有当第i列的j确定时才能完全确定第i-1列选的那些格子），也就是说此时就可以判断第i-1列是否满足只有连续偶数个0，用代码表示为： st[j | k]

完整代码如下：

#include <iostream>
#include <cstring>
using namespace std;

int N, M;
int st[1 << 11 + 10];
long long f[15][(1 << 11) + 10];    // 1 << 11 + 10

int main(){
    while (cin >> N >> M, N || M){
        // 有多组测试样例时一定要考虑是否要重新初始化
        memset(f, 0, sizeof(f));
        // 预处理
        for (int i = 0; i < (1 << N); i ++){  // 遍历每一种状态
            int cnt = 0; bool ok = true;
            for (int j = 0; j < N; j ++){  // 遍历当前状态二进制的每一位
                if ((i >> j) & 1){
                    if (cnt % 2) {ok = false; break;}
                }else cnt ++;
            }if (cnt % 2) ok = false;
            st[i] = ok;
        }


        f[0][0] = 1;  // 易知一开始没有格子伸到第一列(所以用f[0][0]表示)，这也是一种方案(所以f[0][0]=1)
        for (int i = 1; i <= M; i ++){ // 列号从0 ~ M-1, 所以这里其实是从第二列开始的
            for (int j = 0; j < (1 << N); j ++){
                for (int k = 0; k < (1 << N); k ++){
                    if (!(j & k) && st[j | k]) f[i][j] += f[i - 1][k];
                }
            }
        }

        cout << f[M][0] << endl;  // f[M + 1][0]
    }

    return 0;
}