题意描述：

　　给定一块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;
}