题意：给你递推公式要求矩阵快速幂的第n项
解题思路： 经典的矩阵快速幂递推第n项目做法。
解题代码：
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 LL n ,m , d; 27 int ta,tb; 28 struct Matrix 29 { 30 LL mat[15][15]; 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(" "); 42 } 43 } 44 void init() 45 { 46 clear(); 47 for(int i = 0 ;i < n;i ++ ) 48 { 49 scanf("%lld",&mat[0][i]); 50 mat[0][i] %= m ; 51 } 52 for(int i = 1;i < n;i ++) 53 { 54 mat[i][i-1] =1; 55 } 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 ; // 第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;