核心思路：

1. 题目分析

• 摆放方块的时候，先放横着的，再放竖着的。总方案数等于只放横着的小方块的合法方案数。

• 如何判断，当前方案数是否合法？ 所有剩余位置能否填充满竖着的小方块。可以按列来看，每一列内部所有连续的空着的小方块需要是偶数个。

• 这是一道动态规划的题目，并且是一道 状态压缩的dp：用一个N位的二进制数，每一位表示一个物品，0/1表示不同的状态。因此可以用 $0\rightarrow2^N-1(N:二进制对应的十进制数)$ 中的所有数来枚举全部的状态。

2. 状态表示

状态表示：$f[i][j]$ 表示已经将前 $i - 1$ 列摆好了，且从第 $i - 1$ 列，伸出到第 $i$ 列的状态是 $j$ 的所有方案，其中$j$ 是个二进制数，用来表示哪一行的小方块是横着放的，其位数和棋盘的行数一致

3. 状态转移

• 既然第 $i$ 列固定了，我们需要看 第 $i-2$ 列是怎么转移到到第 $i-1$列的（看最后转移过来的状态）。假设此时对应的状态是 $k$（第 $i-2$ 列到第 $i-1$ 列伸出来的二进制数，比如 00100 ），$k$ 也是一个二进制数，$1$表示哪几行小方块是横着伸出来的，$0$表示哪几行不是横着伸出来的。

• 它对应的方案数是 $f[i-1][k]$ ，即前 $i-2$ 列都已经摆完，且从第 $i - 2$ 列伸到第 $i-1$ 列的状态为 $k$ 的所有方案数。

• 这个 $k$ 需要满足什么条件呢？

• 首先 $k$ 不能和 $j$ 在同一行，因为从 $i-1$列到第 $i$ 列是横着摆放的$1\times2$的方块，那么 $i-2$ 列到 $i-1$ 列就不能是横着摆放的，否则就是$1\times3$的方块了！这与题意矛盾。所以 $k$ 和 $j$ 不能位于同一行。

• 既然不能同一行伸出来，那么对应的代码为(k & j) == 0，表示两个数相与，$k$ 和 $j$ 没有一位相同，即没有1行有冲突。

• 既然从第 $i-1$ 列到第 $i$ 列横着摆的，和第 $i-2$ 列到第 $i-1$ 列横着摆的都确定了，那么第 $i-1$ 列 空着的格子就确定了，这些空着的格子将来用作竖着放。如果某一列有这些空着的位置，那么该列所有连续的空着的位置长度必须是偶数。

• 总共 $m$ 列，我们假设列下标从0开始，即第0列，第1列……，第 $m-1$列。根据状态表示 $f[i] [j]$ 的定义，我们答案是什么呢？ 答案是 $f[m][0]$， 意思是前 $m-1$ 列全部摆好,且从第 $m-1$ 列到 $m$ 列状态是0（意即从第 $m-1$ 列到第 $m$ 列没有伸出来的）的所有方案，即整个棋盘全部摆好的方案。

时间复杂度：$O(n\times2^n\times2^n)=11\times2^{11}\times2^{11}≈4\times10^7$