首页 > 代码库 > HDU 2604 Queuing 矩阵快速幂
HDU 2604 Queuing 矩阵快速幂
题意：给你一个01串 ，为你长度为 n且不包含 010,000,这两个串的情况有多少种。
解题思路：
首先 我们假设前把前两个字母的情况列出来
只有4种
00（1） 10（2）
01 （3） 11 （4）
假设我们dp 到了下一个字母
显然 ，（4） 状态只能由 （3） （4） 转移过来
（3） 状态只能由 （2）（1）转移过来
（2） 只能右（4） 转移过来
（1）只能由（2） 转移过来
如果暴力做的话会超时 。。所以我们应该能想到这题是用矩阵快速幂做的，我最开始想到的就是用 2x2 的矩阵去维护， 但
是显然状态很难推，所以我们把我们的初始矩阵变为 4 x 1（都是用一维矩阵保存状态，二维太过繁琐），这样就可以很快的
构造出中间矩阵了。
转载一张图：http://www.cnblogs.com/zfyouxi/p/3774402.html
解题代码：
1 // File Name: temp.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月17日 星期三 11时35分45秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 using namespace std; 26 int n , k,l ,m; 27 struct Matrix 28 { 29 int mat[20][20]; 30 void clear() 31 { 32 memset(mat,0,sizeof(mat)); 33 } 34 void output() 35 { 36 for(int i =0 ;i < n ;i ++) 37 { 38 for(int j = 0 ;j < n ;j ++) 39 printf("%d ",mat[i][j]); 40 printf("\n"); 41 } 42 } 43 void init() 44 { 45 n = 4; 46 clear(); 47 mat[0][0] = 1; 48 mat[0][3] = 1; 49 mat[1][2] = 1; 50 mat[2][0] = 1; 51 mat[3][1] = 1; 52 mat[3][2] = 1; 53 } 54 Matrix operator *(const Matrix &b) const 55 { 56 Matrix ret; 57 ret.clear(); 58 for(int i = 0 ;i < n ;i ++) 59 for(int j = 0;j < n;j ++) 60 { 61 for(int k = 0 ;k < n ;k ++) 62 { 63 ret.mat[i][j] =(ret.mat[i][j] + mat[i][k] * b.mat[k][j]) % m ; // 第I 行 第J 列 64 } 65 } 66 return ret; 67 } 68 }; 69 Matrix Pow( Matrix a ,int t ) 70 { 71 Matrix ret; 72 ret.clear(); 73 for(int i = 0 ;i < n ;i ++) 74 ret.mat[i][i] = 1; 75 Matrix tmp = a; 76 while(t) 77 { 78 if(t&1) ret = ret * tmp; 79 tmp = tmp * tmp; 80 t >>=1; 81 } 82 return ret; 83 } 84 int main(){ 85 while(scanf("%d %d",&l,&m) != EOF) 86 { 87 if(l == 1 ) 88 { 89 printf("2\n"); 90 continue; 91 } 92 if(l == 2) 93 { 94 printf("4\n"); 95 continue; 96 } 97 Matrix a; 98 a.init(); 99 a = Pow(a,l-2);100 int sum = 0 ; 101 for(int i = 0 ;i < n;i ++)102 for(int j =0 ;j < 4;j ++)103 {104 sum += a.mat[i][j];105 }106 sum %= m;107 printf("%d\n",sum);108 }109 return 0;110 }
HDU 2604 Queuing 矩阵快速幂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。