首页 > 代码库 > 点头OJ 1033 . 骨牌覆盖 V2 ( 状态压缩 + 矩阵快速幂 )
点头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 ( 状态压缩 + 矩阵快速幂 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。