题目描述：
给出一个 h*w 的空棋盘，1<=h,w<=11，若用1*2或2*1的骨牌去完全覆盖这个棋盘，问有多少种方法？
题目分析：
规模很小，棋盘的每个格子有覆盖和未覆盖两种，正好对应二进制中的 1 和 0 。所以可以用一个二进制数表示一行棋盘的状态，这称之为状态压缩，然后对其进行相应的位运算，表示相应的操作。
首先，我们明确一下状态的在该题的意义： 若当前格被一个1*2的骨牌盖住，或者被一个2*1的骨牌下面格盖住，则为 1 ；否则为0 。
有了状态，我们就可以得出一些结论：
1.当前行的状态只与上一行有关；
2.若上行某个为0，则下行相应格必须为1；若上行某格为1，则下行相应格可为 0 或1；
这样我们就可以有上一行的状态，递推出下一行的状态了。我们可以先求出所有的用1*2骨牌填一列的状态集M。然后，用每一个状态A去与上行状态判断，若有矛盾，则证明当前行不能为A；否则，A状态的方法数可由上行得出。
用一个方程表示： F[ row , i ] = sum ( f[row - 1 , j ] ) , j表示上行状态，i表示与j无矛盾的状态。
参考程序：
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef __int64 i64;
const int maxn = 1<<12;
const int maxl = 150;
int status , als , n ,h ;
int all[maxl] ; //所有的1*2骨牌填一行的状态，二进制表示
i64 f[maxn] , s[maxn]; // 滚动数组
inline void put(int &bd ,int i) // 覆盖格子
{
if(!( bd & (1<<i) )) bd += 1<<i;
}
inline void clr(int &bd ,int i) //清空格子
{
if( bd & (1<<i) ) bd -= 1<<i;
}
void dfs(int i) //先搜索出用1*2骨牌去填一行，未填为0
{
if(i >= n - 1 )
{
all[als ++ ] = status;
return ;
}
dfs(i + 1);
put(status , i); put(status , i + 1 );
dfs(i + 2);
clr(status , i); clr(status , i + 1 );
}
i64 dp()
{
int i , j , row , son , t , c;
status = als = 0 ; dfs(0) ;
memset(f , 0 ,sizeof(f));
for(i = 0 ; i<als ; ++i) f[ all[i] ] = 1 ; //初始首行
for(row = 1 ; row < h; ++ row)
{
memset(s , 0 , sizeof(s));
for(i = 0 ; i< (1<<n) ; ++i)
if( f[i] != 0 )
{
c = i ^( (1<<n) - 1 ) ; // 对i的后n为取反
for( j = 0 ; j< als ; ++j) // 试探每个状态
if( !( all[j] & c ) ) // 表示无矛盾
{
t = c + all[j] ; // t 为新状态
s[ t ] += f[i]; // 方法数累加
}
}
for(i = 0 ; i< (1<<n) ; ++i)
f[i] = s[i] ;
}
return f[( 1<<n )- 1];
}
int main()
{
while(scanf("%d%d",&h , &n )!=EOF && ( h || n))
printf("%I64d\n",dp());
return 0;
}