点头OJ 1033 . 骨牌覆盖 V2 ( 状态压缩 + 矩阵快速幂 )

题目链接~~>

做题感悟：先前做过一个类似的题，是俄罗斯的一道区域赛的题目，也是用的状态压缩 + 矩阵快速幂。

解题思路：状态压缩 + 矩阵快速幂

                构造一个矩阵 B [ i ] [ j ] 代表状态 i ,与状态 j 是否合法，j 代表上一行的状态，如果合法为 1 ,否则为 0 ，这样如果再得到初始各种状态的方案数的矩阵 A ，A 只有一列 ，这样 B * A 就是第二行各种状态对应 的方案数 。这样再加上矩阵快速幂就解决了。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<bitset>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<cctype>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std  ;
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      #define L(x) (x * 2)
     
    
   

    

     

    
    

     

      #define R(x) (x * 2 + 1)
     
    
   

    

     

    
    

     

      const int INF = 0x3f3f3f3f ;
     
    
   

    

     

    
    

     

      const double esp = 0.00000000001 ;
     
    
   

    

     

    
    

     

      const double PI = acos(-1.0) ;
     
    
   

    

     

    
    

     

      const INT mod = 1000000007 ;
     
    
   

    

     

    
    

     

      const int MY = (1<<5) + 5 ;
     
    
   

    

     

    
    

     

      const int MX = (1<<13) + 5 ;
     
    
   

    

     

    
    

     

      const int S = 20 ;
     
    
   

    

     

    
    

     

      int n ,m ;
     
    
   

    

     

    
    

     

      INT key[50] ;
     
    
   

    

     

    
    

     

      struct M
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       INT p[32][32] ;
     
    
   

    

     

    
    

     

       M()
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 memset(p ,0 ,sizeof(p)) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 void init()
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < (1<<m) ; ++i)
     
    
   

    

     

    
    

     

       p[i][i] = 1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       M operator *(const M& a)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       M c ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < (1<<m) ; ++i)
     
    
   

    

     

    
    

     
 for(int k = 0 ;k < (1<<m) ; ++k)
     
    
   

    

     

    
    

     
 if(p[i][k])
     
    
   

    

     

    
    

     
 for(int j = 0 ;j < (1<<m) ; ++j)
     
    
   

    

     

    
    

     

       c.p[i][j] = (c.p[i][j] + p[i][k]*a.p[k][j])%mod ;
     
    
   

    

     

    
    

     
 return c ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      };
     
    
   

    

     

    
    

     

      M pow(M a ,int k) // 矩阵快速幂
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       M b ;
     
    
   

    

     

    
    

     

       b.init() ;
     
    
   

    

     

    
    

     
 while(k)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(k&1)  b = a * b ;
     
    
   

    

     

    
    

     

       a = a * a ;
     
    
   

    

     

    
    

     

       k >>= 1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return b ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void dfs(int S ,int cnt ,int tx ,int S1 ,M& c)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(cnt == m)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       c.p[S][tx] = 1 ;
     
    
   

    

     

    
    

     
 if(S1 == 0)   key[S] = 1 ;
     
    
   

    

     

    
    

     
 return ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(cnt + 2 <= m && !(S&(1<<cnt)) && !(S&(1<<(cnt+1))))
     
    
   

    

     

    
    

     

       dfs(S|(1<<cnt)|(1<<(cnt+1)) ,cnt+2 ,tx ,S1 ,c) ;
     
    
   

    

     

    
    

     

       dfs(S ,cnt+1 ,tx ,S1 ,c) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 //freopen("input.txt" ,"r" ,stdin) ;
     
    
   

    

     

    
    

     
 while(~scanf("%d%d" ,&n ,&m))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       M c ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < (1<<m) ; ++i)  // 处理各种对应的状态 同时初始化第一行的状态
     
    
   

    

     

    
    

     

       dfs((~i)&((1<<m)-1) ,0 ,i ,(~i)&((1<<m)-1) ,c) ;
     
    
   

    

     

    
    

     

       M b = pow(c ,n-1) ;
     
    
   

    

     

    
    

     

       INT ans = 0 ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < (1<<m) ; ++i)
     
    
   

    

     

    
    

     

       ans = (ans + b.p[(1<<m)-1][i]*key[i])%mod ;
     
    
   

    

     

    
    

     
 cout<<ans%mod<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/41245003