用$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;
}
最后一次更新于2019-10-25
0 条评论