1100.cpp

来自「自己的ac代码 在acm.zju.edu.cn 上的题目」· C++ 代码 · 共 57 行

#include<stdio.h>
#include<string.h>
long long opt[12][1<<11];
int p2[20];
int tot;
int n,m;
void Search(int i,int j,long long v,int dep)
{
	if(dep>=m)
	{
		opt[i+1][tot]+=v;
	}
	else
	{
		if(j & p2[dep])Search(i,j,v,dep+1);
		else
		{
			tot+=p2[dep];
			Search(i,j,v,dep+1);
			tot-=p2[dep];
			if(dep+1<m && (j&p2[dep+1])==0)
			{
				//tot+=p2[dep]+p2[dep+1];
				Search(i,j,v,dep+2);
				//tot-=p2[dep]+p2[dep+1];
			}
		}
	}
}



int main()
{
	int i,j,k;
	for(i=0;i<20;i++)p2[i]=1<<i;

	
	while(scanf("%d%d",&n,&m))
	{
		if(n==0 && m==0)break;
		memset(opt,0,sizeof(opt));
		opt[0][0]=1;
		for(i=0;i<n;i++)
		{
			tot=0;
			for(j=0;j<(1<<m);j++)
				Search(i,j,opt[i][j],0);
		}
		printf("%lld\n",opt[n][0]);

	}
	return 0;
}