蒙德里安的猜想

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

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

输入格式

输入包含多组测试用例。

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

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

输出格式

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

数据范围

$1\leq N,M\leq 11$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
输入样例：
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 ~ 11 ，考虑进行状压dp

棋盘面积一定是偶数，否则不存在合法方案（本题保证一定合法）；

长方形的放置只存在横向和纵向两种方案，现只考虑横向放置长方形。当所有横向长方形防止完毕，纵向方案唯一确定。故只需考虑横向放置即可；

$f[i][j]$表示前$i-1$列已经放置好，且从第$i-1$列延伸出来的$1 \times 1$的小正方形的排列方式为$j$（$j$看成$n$位二进制数，第$d$行存在延伸过来的小正方形，则$j$的第$d$位为$1$，否则为$0$）的所有方案数；

状态转移：考虑由$f[i-1][k]$转移。合法的转移情况保证$j$和$k$的同一数位不能都是$1$，否则会发生重叠；并且当第$i$列、第$i-1$列放置完后，不允许存在由连续奇数行没有横向长方形；

对应上述两种情况，保证 i & k == 0 且 i | k 中没有连续奇数个0。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 12,M = 1 << N;    //N行，M中状态

int n,m;
bool st[M]; //预处理所有合法状态
LL f[N][M];

int main() {
    while(cin >> n >> m,n || m) {
        for(int i = 0; i < 1 << n; ++ i) {
            int cnt = 0;    //统计连续0
            st[i] = true;
            for(int j = 0; j < n; ++ j) 
                if(i >> j & 1) {
                    if(cnt & 1) st[i] = false;  //连续奇数个0，状态不合法
                    cnt = 0;
                }
                else ++ cnt;
            if(cnt & 1) st[i] = false;  //注意末尾可能存在奇数个0
        }
        //初始化f数组
        for(int i = 0; i <= m; ++ i)
            for(int j = 0; j < 1 << n; ++ j)
                f[i][j] = 0;
        //f[0][0]什么都没放置，仅一种方案        
        f[0][0] = 1;
        //枚举第i列的所有状态可以由i-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] += (LL)f[i-1][k];
        //f[m][0]表示前m-1列放好，且第m列没有任何延伸。注意，数组从0开始
        printf("%lld\n",f[m][0]);
    }
    return 0;
}