题解：蒙德里安的梦想
注：
本题解内容简陋，多有不周，敬请谅解。如果有问题请在评论区留言。谢谢。由于作者能力有限，这篇题解不会给出太严谨的证明，只是旨在帮助大家更好地理解此题，具体的做法请读者自己思考。
题目简述:
求把 \(N×M\) 的棋盘分割成若干个 \(1×2\) 的长方形，有多少种方案。
如下图所示：
当 \(N=2,M=4\) 时，共有上图所示的五种方案
解题大概思路
首先，对于方案数的计算，可以考虑搜索枚举以计算答案。但是，考虑到搜索的复杂度是指数级别的（很抱歉，这里没能够想出复杂度是多少，如果有同学计算出来了可以在评论区留言），不能够通过 \(N \leq 11\) 的数据范围。于是我们需要考虑优化搜索算法。
如果大家看过闫老师的 \(DP\) 问题分析课，就会发现 \(DP\) 实际上就是对搜索的优化（其中一种实现方式就是记忆化搜索）。所以，对于这一道题，我们可以考虑使用动态规划算法来解决。
闫氏 \(DP\) 分析法主要分为两大步骤：状态表示和状态计算。在大概思路里我们只讨论状态表示。我们考虑一列一列地放置长方形（我也不清楚为什么要这样表示状态，暂时将其理解为这种 棋盘式动态规划问题 的一种套路）。那么，某一列放置的方案只与上一列的放置方案有关（至于为什么接下来会进行详细说明）。为了方便记录状态，我们考虑使用状态压缩的方式存储状态。于是就有了本题的大概思路：状态压缩动态规划。
算法设计
我们考虑使用闫氏 \(DP\) 分析法来解决此题：
以上的描述可能过于模糊。我们来举一个例子看一看：
左侧表示状态 \(f[2][0]\) （请注意，我们行和列的编号都从 \(0\) 开始，二进制表示第 \(0\) 行为 \(2^0\) ，第 \(i\) 行为 \(2^i\) ），它可以从右侧（可能不只）的三个状态转移过来: \(f[1][4],f[1][7],f[1][1]\) 。
那么如何判断一个状态 \(f[i][state]\) 是否可以由状态 \(f[i-1][j]\) 转移而来呢？
结论是，当且仅当以下条件成立:
- \(state ~ \& ~ j = 0\)
- \(state ~ | ~ j\) 每一段连续的 \(0\) 都是偶数个
接下来我们来不严谨地粗略证明以下以上结论。
我们要证明的命题是，\(j\) 状态可以由 \(state\) 状态演变而来，并且有且仅有一种演变方案，当且仅当我们说到的上述条件成立。即
\[j状态可以由state状态演变而来，并且有且仅有一种演变方案\Leftrightarrow 上述条件成立 \]我们需要证明以下命题：
\[\tag{1}j~状态可以由~state~状态演变而来，并且有且仅有一种演变方案\rightarrow 上述条件成立 \]\[\tag{2}j~状态可以由~state~状态演变而来，并且有且仅有一种演变方案\leftarrow 上述条件成立 \]我们先证明命题 \((1)\) ：
如果说 \(j\) 状态可以由 \(state\) 状态演变而来，并且有且仅有一种演变方案，那么上述条件成立.
我们先说一说 \(state~\&~j = 0\) 等价于什么。这等价于 \(state\) 和 \(j\) 不能在同一位上同时都是一（这里就不给出严格证明了）。我们又可以知道，状态上某一位为一，意味着这一位对应的方格放置的是一个横向的小长方形（这里也不给出严格证明，读者可以自己想想为什么）。也就是说， \(state~\&~j = 0\) 保证了两个小方块重叠的情况不会发生。我们可以大概感受一下，如果说 \(j\) 状态可以由 \(state\) 状态演变而来，那么重叠的情况是不会发生的。
我们再说一说 \(state~|~j\) 代表着什么。 \(state~|~j\) 上某一位为零等价于 \(state\) 和 \(j\) 在这一位上都不为零，也就等价于这一位上没有摆放长方形。我们考虑先摆放横着的长方形再摆放竖着的长方形，那么如果连续的 \(0\) 是奇数个，我们从感觉上可以感知到这种情况是不可能用竖着的小方块铺满的（这里也不给出严格证明）。所以说，如果说命题 \((1)\) 是成立的。
我们再来证明命题 \((2)\) ：
如果上述条件成立，那么存在且仅存在一种摆放横向小方格的方式，并且剩余部分可以由纵向的小方格铺满，并且纵向摆放的方式也有且仅有一种（感觉上应该是这样的），那么 \((2)\) 也是成立的。
于是对于某一个状态 \(state\) ，我们可以枚举每一个状态 \(j\) ，如果说 \(state\) 和 \(j\) 满足以上条件，那么 \(f[i][state]\)+=\(f[i-1][j]\)
完整代码
代码如下：
#include<iostream>
#include<bitset>
#include<vector>
#include<cstring>
#define f_inline inline __attribute__((always_inline))
using namespace std;
using UL=unsigned long;
using ULL=unsigned long long;//用于存储大型非负整数
bitset<2050> isValid;
vector<UL> partner[2050];//partner[i]存储i所对应的合法的状态
ULL f[15][2050];
f_inline bool check(register const UL num,register const UL N)//i是一个N位二进制数,返回值等价于num是否合法，即所有连续的0都是偶数个
{
register UL cnt(0);
for(register UL i(0);i<N;++i)
if((num>>i)&1)
{
if(cnt&1)
return false;
cnt=0;
}
else
++cnt;
return !(cnt&1);
}
int main()
{
register UL N,M;
while(cin>>N>>M,N||M)
{
register const UL bound(1<<N);//常量UL形式存储上限的值
//初始化对于每一个状态是否合法的判定数组
for(register UL i(0);i<bound;++i)
check(i,N)?isValid.set(i):isValid.reset(i);
//初始化对于每一个状态可以转移到其的状态,用于优化代码常数
for(register UL i(0);i<bound;++i)
{
partner[i].clear();
for(register UL j(0);j<bound;++j)
if((!(j&i))&&isValid.test(j|i))
partner[i].emplace_back(j);
}
memset(f,0,sizeof(f)),//f数组初始化赋值为0
f[0][0]=1;//第0列状态为0有且仅有一种方案，就是一块也不放
for(register UL i(1);i<=M;++i)
for(register UL j(0);j<bound;++j)
if(!partner[j].empty())
for(register vector<UL>::iterator it(partner[j].begin());it!=partner[j].end();++it)
f[i][j]+=f[i-1][*it];
cout<<f[M][0]<<endl;//f[M][0]就是最终的答案
}
return 0;
}