首页 > 代码库 > POJ 3233 Matrix Power Series 矩阵快速幂 + 二分
POJ 3233 Matrix Power Series 矩阵快速幂 + 二分
题意：求矩阵的次方和
解题思路：最容易想到方法就是两次二分因为 我们可以把一段 A^1 + A^2 + .......A^K 变成 A^1 + ..A^(K/2) +( A^1 + ..A^(K/2))*(A^(k/2)) 当k 为奇数的时候 或者 A^1 + ..A^(K/2) +( A^1 + ..A^(K/2))*(A^(k/2)) + A^K 当K 为偶数的时候。
解题代码：
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 ,m , k ; 27 int ta,tb; 28 struct Matrix 29 { 30 int mat[30][30]; 31 void clear() 32 { 33 memset(mat,0,sizeof(mat)); 34 } 35 void output() 36 { 37 for(int i =0 ;i < n ;i ++) 38 { 39 for(int j = 0 ;j < n ;j ++) 40 printf("%d ",mat[i][j]); 41 printf("\n"); 42 } 43 } 44 void init() 45 { 46 clear(); 47 for(int i = 0 ;i < n;i ++) 48 for(int j = 0 ;j < n;j ++) 49 { 50 scanf("%d",&mat[i][j]); 51 } 52 } 53 Matrix operator *(const Matrix &b) const 54 { 55 Matrix ret; 56 ret.clear(); 57 for(int i = 0 ;i < n ;i ++) 58 for(int j = 0;j < n;j ++) 59 { 60 for(int s = 0 ;s < n ;s ++) 61 { 62 ret.mat[i][j] =(ret.mat[i][j] + mat[i][s] * b.mat[s][j]) % m ; // 第I 行 第J 列 63 } 64 } 65 return ret; 66 } 67 Matrix operator *(const int &b) const 68 { 69 Matrix ret; 70 ret.clear(); 71 for(int i = 0 ;i < n ;i ++) 72 for(int j = 0;j < n;j ++) 73 { 74 ret.mat[i][j] = (mat[i][j] * b) % m ; // 第I 行 第J 列 75 } 76 return ret; 77 } 78 Matrix operator +(const Matrix &b) const 79 { 80 Matrix ret; 81 ret.clear(); 82 for(int i = 0 ;i < n ;i ++) 83 for(int j = 0;j < n;j ++) 84 { 85 ret.mat[i][j] = (mat[i][j] + b.mat[i][j]) % m ; // 第I 行 第J 列 86 } 87 return ret; 88 } 89 }; 90 Matrix Pow( Matrix a ,LL t ) 91 { 92 Matrix ret; 93 ret.clear(); 94 for(int i = 0 ;i < n ;i ++) 95 ret.mat[i][i] = 1; 96 Matrix tmp = a; 97 while(t) 98 { 99 if(t&1) ret = ret * tmp;100 tmp = tmp * tmp;101 t >>=1;102 }103 return ret;104 }105 Matrix add(Matrix a, int k )106 {107 Matrix ans;108 ans.clear();109 if(k == 1)110 {111 return a;112 }113 if(k&1)114 {115 Matrix temp = add(a,k/2);116 ans = temp + temp * Pow(a,k/2) + Pow(a,k);117 }else{118 Matrix temp = add(a,k/2);119 ans = temp + temp * Pow(a,k/2);120 }121 return ans ; 122 }123 int main(){124 LL l ;125 while(scanf("%d %d %d",&n,&k,&m) != EOF)126 {127 Matrix a;128 a.clear();129 a.init();130 a = add(a,k);131 //a.output();132 a.output();133 }134 return 0;135 }
写完以后过了竟然跑了 1300+ms 最快 0ms 不能忍上网查题解 发现了这种方法 ：http://www.cnblogs.com/rainydays/archive/2011/02/21/1960189.html
他的主要思想是多加 n维度 构成一个能累加的矩阵 ，具体看博主题解。
这种思想很巧妙。
POJ 3233 Matrix Power Series 矩阵快速幂 + 二分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。