题意：给定n,m的矩阵，就是求稳定的骨牌完美覆盖,也就是相邻的两行或者两列都至少有一个骨牌
分析：第一步：
如果是单单求骨牌完美覆盖，请先去学基础的插头dp(其实也是基础的状压dp)骨牌覆盖
hihocoder有全套课程：骨牌覆盖（一, 二，三），状态压缩（二）
学好了以后，首先打一个预处理没有限制的表，由于赛后补题，我就没自己打，直接从网上粘的表
我的表来自：http://blog.csdn.net/u012015746/article/details/51971977
第二步：
这就是容斥的过程了，我们可以枚举每种列分割状态，计算出每种列分割状态下行合法的方案数
然后用总数，减去一个列分割数为1的，加上列分割数为2.........这就是容斥的过程了
细节处理：每种列状态下如何求合法的行状态呢，每种状态在用一下递推一下就好了（枚举依据是前j行无行分割，后i-j行有行分割）
其实是枚举的第一个行分割线出现的位置，上面不能有，下面就可以随意了
详情请参考上面的链接
复杂度：O（T*(n^2)*(2^m))，大概是这个复杂度
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1e9+;
LL RES[][];
void init();
LL dp[];
LL solve(int n,int m){
int pos[],tot=(<<(m-));
LL ret=;
for(int cur=;cur<tot;++cur){
int cnt=;pos[cnt]=;
for(int i=;i<m-;++i)if(cur&(<<i))pos[++cnt]=i+;
pos[++cnt]=m;
for(int i=cnt;i>;--i)pos[i]-=pos[i-];
for(int i=;i<=n;++i){
for(int j=;j<i;++j){
LL tmp=;
for(int k=;k<=cnt;++k)
tmp=tmp*RES[i-j][pos[k]]%mod;
if(!j)dp[i]=tmp;
else dp[i]=(dp[i]-tmp*dp[j]%mod+mod)%mod;
}
}
if(cnt&)ret=(ret-dp[n]+mod)%mod;
else ret=(ret+dp[n])%mod;
}
return ret;
}
int main(){
init();
int n,m;
while(~scanf("%d%d",&n,&m)){
printf("%I64d\n",solve(n,m));
}
return ;
}
void init()
{
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
}