用$f_{i,k}$表示第$i$行状态为$k$,$k$的定义是这样的:

在二进制下第$c$位为$1$时,表示一个竖着的长方形的上半部分,否则表示其他状态(竖着的下半部分,横着的左半部分,横着的右半部分)。

那么如果$f_{i-1,k}$的$k$在第$c$位表示为$1$,那么紧接着第$i$行的状态$j$的第$c$位应为$0$,才符合状态转移。

因此需要满足第$i$行与第$i-1$行需满足$j\&k==0$这一条件,才有可能进行状态转移。

如果$f_{i-1,k}$的$k$在第$c$位表示为$0$,如果对应第$i$行,会有如下几种状态:

第$c$位为$1$,也就是没什么关系,不属于同一个长方形,符合转移。

第$c$位为$0$,也就是$i-1,i$行的第$c$位均属于横着的长方形的一部分。

那么根据这些状态,是否可以猜想出什么?

将$j|k$表示出来,那么每一段连续的$0$,也就是$i-1$和$i$行的第$c$位都为$0$的情况,也就是两行均为横着的长方形的一段中,需要满足每一段连续的$0$的个数,都必须是偶数,才能满足形成若干个横着的长方形,奇数个是不可能形成若干个完整的横长方形的。

因此,需要预处理出$[0,2^{m}-1]$内所有满足"二进制表示每一段连续的$0$都有偶数个"的整数,记录在集合$S$中。

所以转移方程就为:

$$f_{i,j}=\sum\limits_{j\&k==0~and ~j|k\in S}f_{i-1,k}$$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define gc getchar()
#define ll long long
using namespace std;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar(x%10+48);
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll f[12][1<<11],ans[12][12];bool v[1<<11];//1 竖上半,0 其他状态,j&k==0(竖)&&v[j|k]==1(横) 
int main()
{
    for(int m=1;m<=11;m++)
    {
        for(int i=0;i<1<<m;i++)
        {
            bool bk_odd=0,cnt=0;
            for(int j=0;j<m;j++)
            {
                if(i>>j&1)bk_odd|=cnt,cnt=0;
                else cnt^=1;
            }
            v[i]=bk_odd|cnt?0:1;//最后那次还没或
        }
        f[0][0]=1;
        for(int i=1;i<=11;i++)
        {
            for(int j=0;j<1<<m;j++)
            {
                f[i][j]=0;
                for(int k=0;k<1<<m;k++)
                    if(((j&k)==0)&&v[j|k])
                        f[i][j]+=f[i-1][k];
            }
            ans[i][m]=f[i][0];
        }
    }
    int n,m;
    while(qr(n),qr(m),n)qw(ans[n][m]),puts("");
    return 0;
}