问题描述：

给定m×n个格子，每个格子被染成了黑色或白色。现在要用1×2的砖块覆盖这些格子，要求快于快之间互相不重叠，且覆盖了所有白色的格子（用 . 表示），但不覆盖任意一个黑色的格子（用 x 表示）。求一共有多少种覆盖方法，输出方案数对M取余后的结果。

首先考虑一下枚举所有的解法这一方法。为了不重复统计，我们每次从最左上方的空格处开始放置。对于哪些格子已经被覆盖过了，我们只需要用一个bool数组来维护即可，即:

#include
    
     #include
     
      #include
      
       using namespace std;int n,m,M;char tu[20][20];bool used[20][20];int rec(int i,int j,bool used[20][20]){    if(j==m)///当前这一行已经走完了    {        return rec(i+1,0,used);    }    if(i==n)///已经把整个图都走完了    {        return 1;    }    if(used[i][j]||tu[i][j]=='x')///当这个点已经放过或者说是黑色的，则不需要放置地砖    {        return rec(i,j+1,used);    }    int res=0;    used[i][j]=true;///标记这个点已经放过了    ///横着放    if(j+1
      
     
    

这个方法无法在规定的时间内求出答案。而且递归的参数共有n×m×2^nm种可能，也无法使用记忆话搜索。

首先，由于黑色的格子不能被覆盖，因此used里对应的 位置总是false。对于白色的格子，如果要在（i，j）位置上放置砖块，那么由于总是从最左上方可以放的位置开始放，那么对于（i'，j'）<（i，j）（按字典序比较）的（i'，j'）总有used[i'][j']=true成立。

此外，由于砖块的大小为1×2，因此对于每一列j'在满足（i'，j'）>=（i，j）的所有i'中，除了最小的i‘之外，都满足used[i'][j']=false。因此，不确定的只有每一列里还没有查询格子中最上面的一个，共m个。从而把这m个格子通过状态压缩编码进行记忆化搜索，复杂度为（n×m×2^m）。

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int n,m,M;char tu[20][20];//bool used[20][20];int dp[2][1<<20];void solve(){    int *crt=dp[0],*next=dp[1];    crt[0]=1;    for(int i=n-1; i>=0; i--)    {        for(int j=m-1; j>=0; j--)        {            for(int used=0; used<1<
        
         >j&1)||tu[i][j]=='x')                {                    next[used]=crt[used&~(1<
         
          >(j+1)&1)&& tu[i][j+1]=='.') { res+=crt[used|1<<(j+1)]; } ///竖着放 if(i+1