题目描述

求把 $N \times M$ 的棋盘分割成若干个 $1 \times 2$ 的长方形，有多少种方案。

例如当 $N=2，M=4$ 时，共有 $5$ 种方案。当 $N=2，M=3$ 时，共有 $3$ 种方案。

如下图所示：

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含两个整数 $N$ 和 $M$。

当输入用例 $N=0，M=0$ 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个结果，每个结果占一行。

数据范围

$1 \le N,M \le 11$

输入样例：

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例：

1
0
1
2
3
5
144
51205

算法

先放横着的,再放竖着的,横着放完竖着方案就确定好了（保证横着放后竖条可以正确放入）。故总方案数等于只放着横着的小方块的方案数。

当前列的状态由二进制数表示，从低位到高位表示从上到下的每一行是否放置横条

判断当前方案是否合法：一列一列来看，保证1.当前列和前一列不能有冲突 2.当前列不能有偶数个空位

)

时间复杂度 $\mathcal{O}(M\cdot2^{N+M})$

优化：可以先预处理出合法的不含奇数个0的方案和连续两列合法的方案。另外n*m为奇数则没有合法方案，直接输出0。因为放入的小块是1*2，如果n*m不是2的倍数不可能正好放下。

C++ 代码

曾经写了非常多的注释，这里不做删除。

/*
 * @Author: ACCXavier
 * @Date: 2021-05-01 20:32:09
 * @LastEditTime: 2023-01-15 22:09:23
 * Bilibili:https://space.bilibili.com/7469540
 * 题目地址:https://www.acwing.com/problem/content/293/
 * @keywords: 蒙德里安的梦想
 * https://www.acwing.com/solution/content/28088/
 */

#include <bits/stdc++.h>
using namespace std;

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

long long f[N][M];  //@第二维为M,开longlong 第一维表示列， 第二维表示所有可能的状态

bool st[M];  //@M种状态 存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true。

//vector<int > state[M];  //二维数组记录合法的状态
vector<vector<int>> state(M);  //小括号，表示M行数组，列数不定（写成大括号就变成三维数组)
int m, n;

int main() {
    while (cin >> n >> m, n || m) {  //读入n和m，并且不是两个0即合法输入就继续读入
        if((n * m) & 1) {
            puts("0"); continue;
        }
        //第一部分：预处理1
        //对于每种状态，先预处理每列不能有奇数个连续的0
        for (int i = 0; i < 1 << n; i++) {
            int cnt = 0;                   //记录连续的0的个数
            bool isValid = true;           // 某种状态没有奇数个连续的0则标记为true
            for (int j = 0; j < n; j++) {  //遍历这一列，从上到下
                if (i >> j & 1) {          //i>>j位运算，表示i（i在此处是一种状态）的二进制数的第j位； &1为判断该位是否为1，如果为1进入if
                    if (cnt & 1) {         //这一位为1，看前面连续的0的个数，如果是奇数（cnt &1为真）则该状态不合法
                        isValid = false;
                        break;
                    }
                    cnt = 0;  // 既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清零。
                } else
                    cnt++;  //否则的话该位还是0，则统计连续0的计数器++。
            }
            if (cnt & 1) isValid = false;  //最下面的那一段判断一下连续的0的个数
            st[i] = isValid;               //状态i是否有奇数个连续的0的情况,输入到数组st中
        }

        //第二部分：预处理2
        //经过上面每种状态 连续0的判断，已经筛掉一些状态。
        //下面来看进一步的判断：看第i-2列伸出来的和第i-1列伸出去的是否冲突
        for (int j = 0; j < 1 << n; j++) {      //对于第i列的所有状态
            state[j].clear();                   //因为有多组输入样例,清空上次操作遗留的状态，防止影响本次状态。
            for (int k = 0; k < 1 << n; k++) {  //对于第i-1列所有状态
                if ((j & k) == 0 && st[j | k])  // 第i-2列伸出来的 和第i-1列伸出来的不冲突(不在同一行)
                                                //解释一下st[j | k]
                                                //已经知道st[]数组表示的是这一列没有连续奇数个0的情况，
                                                //我们要考虑的是第i-1列（第i-1列是这里的主体）中从第i-2列横插过来的，还要考虑自己这一列（i-1列）横插到第i列的
                                                //比如 第i-2列插过来的是k=10101，第i-1列插出去到第i列的是 j =01000，
                                                //那么合在第i-1列，到底有多少个1呢？自然想到的就是这两个操作共同的结果：
                                                //两个状态或。 j | k = 01000 | 10101 = 11101
                                                //这个 j|k 就是当前 第i-1列的到底有几个1，即哪几行是横着放格子的

                    state[j].push_back(k);  //二维数组state[j]表示二位数组中的第j行，
                                            //j表示 第i列“真正”可行的状态，如果第i-1列的状态k和j不冲突则压入state数组中的第j行。
                                            //“真正”可行是指：既没有前后两列伸进伸出的冲突；又没有连续奇数个0。
            }
        }

        //第三部分：dp开始
        memset(f, 0, sizeof f);  //全部初始化为0，因为是连续读入，这里是一个清空操作。类似上面的state[j].clear()
        f[0][0] = 1;             // 这里需要回忆状态表示的定义，按定义这里是：前第-1列都摆好，且从-1列到第0列伸出来的状态为0的方案数。
        //首先，这里没有-1列，最少也是0列。其次，没有伸出来，即没有横着摆的。即这里第0列只有竖着摆这1种状态。

        for (int i = 1; i <= m; i++) {          //遍历每一列:第i列合法范围是(0~m-1列)
            for (int j = 0; j < 1 << n; j++) {  //遍历当前列（第i列）所有状态j
                for (auto k : state[j])         // 遍历第i-1列的状态k，如果“真正”可行，就转移
                    f[i][j] += f[i - 1][k];     // 当前列的方案数就等于之前的第i-1列所有状态k的累加。
            }
        }

        //最后答案是什么呢？
        //f[m][0]表示 前m-1列都处理完，并且第m-1列没有伸出来的所有方案数(第m列不能再放了)。
        //即整个棋盘处理完的方案数

        cout << f[m][0] << endl;
    }
}