本文主要是介绍点头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 ;
}
这篇关于点头OJ 1033 . 骨牌覆盖 V2 ( 状态压缩 + 矩阵快速幂 )的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
