首页 > 代码库 > HDU 3306 Another kind of Fibonacci 矩阵快速幂
HDU 3306 Another kind of Fibonacci 矩阵快速幂
题意：给你 a[n] = x*a[n-1] + y*a[n-2] ,求 a[n]^2 的前 n项和 S(n)
解题思路：还是没有能理解矩阵快速幂的精髓，每做一题就要多学一点，这个题目并没有直接要到 a[n] a[n-1] 这写东西
而是直接找其中的关联性的东西
a[n]^2 = xx * a[n-1]^2 + yy a[n-2]^2 + 2 * x * y *a[n-1] * a[n-2];
a[n][n-1] = a[n-1]^2 * x + y *a[n-1][n-2];
找到这些公式，我们就能够快速求出矩阵快速幂了
解题代码：
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 #define m 10007 26 using namespace std; 27 LL n,x,y ,k ; 28 struct Matrix 29 { 30 LL mat[4][4]; 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("%lld ",mat[i][j]); 41 printf("\n"); 42 } 43 } 44 void init() 45 { 46 clear(); 47 mat[0][0] = (x*x ) %m ; 48 mat[0][1] = y * y %m ; 49 mat[0][2] = 2*x* y%m; 50 mat[1][0] = 1; 51 mat[2][0] = x; 52 mat[2][2] = y; 53 mat[3][0] = 1; 54 mat[3][3] = 1; 55 n = 4 ; 56 } 57 Matrix operator *(const Matrix &b) const 58 { 59 Matrix ret; 60 ret.clear(); 61 for(int i = 0 ;i < n ;i ++) 62 for(int j = 0;j < n;j ++) 63 { 64 for(int s = 0 ;s < n ;s ++) 65 { 66 ret.mat[i][j] =(ret.mat[i][j] + mat[i][s] * b.mat[s][j] %m ) %m ; // 第I 行 第J 列 67 } 68 } 69 return ret; 70 } 71 }; 72 Matrix Pow( Matrix a ,LL t ) 73 { 74 Matrix ret; 75 ret.clear(); 76 for(int i = 0 ;i < n ;i ++) 77 ret.mat[i][i] = 1; 78 Matrix tmp = a; 79 while(t) 80 { 81 if(t&1) ret = ret * tmp; 82 tmp = tmp * tmp; 83 t >>=1; 84 } 85 return ret; 86 } 87 int main(){ 88 89 while(scanf("%lld %lld %lld",&k,&x,&y) != EOF) 90 { 91 x %= m; 92 y %= m; 93 Matrix a; 94 a.init(); 95 //a.output(); 96 a = Pow(a,k); 97 //a.output(); 98 LL ans = (a.mat[3][0] + a.mat[3][1] + a.mat[3][2] + a.mat[3][3] ) %m ; 99 printf("%lld\n",ans);100 }101 return 0;102 }
HDU 3306 Another kind of Fibonacci 矩阵快速幂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。