题意描述：
给定一块n*m的区域，用1*2的长方形填充，长方形可以横着或竖着摆，问一共有多少种填充方案
具体思路：
题意没什么好说的，简单易懂，很经典的一类状态压缩问题（在棋盘中求填充方案）。
观察数据，满足n，m都比较小，但是搜索的复杂度大到无法接受，考虑使用状态压缩求解此类问题
首先，肯定是第一步，即对题目给定的图进行初始化，初始化应该怎么搞？观察到若使用横着填的方法填充一行的情况，发现有很多单行中有奇数数量的横向填充方案完全不合法，考虑初始化。即预处理出合理的情况，用桶来记录，稍后再筛选出合法的情况。
第一步筛选完成了，虽然排除了许多冗余的情况，但是如此大的数据直接dp，两个指数级别的数相乘会导致复杂度完全无法接受，所以考虑第二步初始化，即将本行的状况与上一行进行比对，确定最终到底有几个合法的情况。
最后一步进入正题，dp环节，dp环节和为什么这样转移在代码中解释
代码实现：
#include<bits/stdc++.h> using namespace std; const int N=1<<13; long long dp[13][N],n,m; bool st[N];//桶数组判断合法状态 vector<vector<long long> >G(N);//第二步筛选后的合法状态 int main() { while(cin>>n>>m,n||m) { for(int i=0;i<(1<<n);i++) { int cnt=0;bool isvalid=true;//记录当前有几个0 for(int j=0;j<n;j++) { if((i>>j)&1)//取出当前为的值，如果当前位为一，之前的cnt记录的"0"的个数清空，接着判断当前状态是否合法 { if(cnt&1)//如果cnt为偶数，不合法 { isvalid=false; break; } cnt=0;//清空不清空差不多 } else cnt++;//当前位为“0”，继续累加 } if(cnt&1) isvalid=false;//判断最后一行是什么情况 st[i]=isvalid; } for(int j=0;j<(1<<n);j++) { G[j].clear();//初始化 for(int k=0;k<(1<<n);k++) {
//细说st[j|k]，关键至极
//首先，j&k是判断是否是上一行是"1",下一行是"0"，因为不是这样就不合法，简言之，只要j&k==1就不合法
//再就是st[j|k]
//首先要了解一点，就是k枚举的是上一行的所有状态，所以st[j|k]是什么意思呢
//明确，st存的是所有合法的状态，如果j|k它不是一个合法的状态，即此时会有奇数个零，那么实际上这个状态它是不合法的，即上一行伸长下来和这一行伸长下去的，这些被伸长或者伸长下去的
//是不能供横着放的格子放的
//所以要这样 if((j&k)==0&&st[j|k]) { G[j].push_back(k); } } } memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=m;i++) { for(int j=0;j<(1<<n);j++) { for(auto k:G[j]) { dp[i][j]+=dp[i-1][k];//当前行的状态的答案是上一行所有可能情况的和 } } } cout<<dp[m][0]<<endl;//答案就是已经填到m行，且当前行没有向下伸长的情况 } return 0; }