Rockdu's Blog

Description

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways. 

Expert as he was in this material, he saw at a glance that he'll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won't turn into a nightmare!

Input

Output

For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

Sample Input

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

Sample Output

1
0
1
2
3
5
144
51205

Source

很早以前写的轮廓线，一直TLE着，今天卡了波常数就A了。

这一类DP我们用dp[i][mask]表示轮廓上空位在mask状态时，到第i个格子的放置方法。注意到我们每一次只会从上一个格子（上方一个或者上一行最后一个）转移过来，我们可以用滚动数组优化。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=11;
LL dp[2][1<<(maxn+1)];
int n,m,i,j,now,news;//n行m列  

bool getbit(int num,int k){  //从第0开始 
	return num&(1<<k);
}

void editbit(int & num,int k,bool val){
	int ret;
	ret=num-(getbit(num,k)<<k)+(val<<k);
	num=ret;
}

int rt(int num){
	return (num>>=1);
}

int main(){
	while(1){
		memset(dp,0,sizeof(dp));
		scanf("%d%d",&n,&m);
		if(n==0 && m==0)	break;
		if(n>m) swap(n,m);
		int ini=(1<<n)-1;editbit(ini,n-1,0);
		dp[0][ini]=1, now = 0;
		for(register int i=0;i<m;i++)
			for(register int j=0;j<n;j++){
				if(i==0 && j==0) continue;
				now ^= 1;
				memset(dp[now], 0, sizeof(dp[now]));
				for(register int k=0;k<1<<n;k++){
					if(getbit(k,0)==0)
						news=k>>1,editbit(news,n-1,1),dp[now][news]+=dp[now ^ 1][k];
					if((getbit(k,0)==1 || i==0) && (getbit(k,n-1)==0 && j!=0))
						news=k>>1,editbit(news,n-2,1),editbit(news,n-1,1),dp[now][news]+=dp[now ^ 1][k];
					if(getbit(k,0)==1 || i==0)
						news=k>>1,dp[now][news]+=dp[now ^ 1][k];						
				}
			} 
		printf("%lld\n",dp[now][(1<<n)-1]);
	}
	return 0;
}