本文共 2260 字，大约阅读时间需要 7 分钟。
题意：中文不说了
解题思路：矩阵快速幂求和。我们可以知道我们可以用矩阵快速幂求他的F[n],显然，每多出一个F[n] 我们就要把它加入到我们的和里面，但是 因为我们是快速幂，不能求出所有的f[n]，所以我们只能多加一维矩阵来维护和。
中间矩阵
3 2 7 0
1 0 0 0
0 1 0 0
1 0 0 1（和）
初始矩阵
5
3
1
4 （前两项的和）
解题代码：
1 // File Name: temp.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月17日 星期三 11时35分45秒 4 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #define LL long long 25 #define m 2009 26 using namespace std; 27 int n ; 28 struct Matrix 29 { 30 int 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("%d ",mat[i][j]); 41 printf("\n"); 42 } 43 } 44 void init() 45 { 46 clear(); 47 n = 4 ; 48 mat[0][0] = 3; 49 mat[0][1] = 2; 50 mat[0][2] = 7; 51 mat[1][0] = 1; 52 mat[2][1] = 1; 53 mat[3][0] = 1; 54 mat[3][3] = 1; 55 } 56 Matrix operator *(const Matrix &b) const 57 { 58 Matrix ret; 59 ret.clear(); 60 for(int i = 0 ;i < n ;i ++) 61 for(int j = 0;j < n;j ++) 62 { 63 for(int k = 0 ;k < n ;k ++) 64 { 65 ret.mat[i][j] =(ret.mat[i][j] + mat[i][k] * b.mat[k][j]) % m ; // 第I 行 第J 列 66 } 67 } 68 return ret; 69 } 70 }; 71 Matrix Pow( Matrix a ,LL t ) 72 { 73 Matrix ret; 74 ret.clear(); 75 for(int i = 0 ;i < n ;i ++) 76 ret.mat[i][i] = 1; 77 Matrix tmp = a; 78 while(t) 79 { 80 if(t&1) ret = ret * tmp; 81 tmp = tmp * tmp; 82 t >>=1; 83 } 84 return ret; 85 } 86 int main(){ 87 int l ; 88 int ca = 0 ; 89 int t ; 90 scanf("%d",&t); 91 while(t--) 92 { 93 ca ++; 94 scanf("%d",&l); 95 int tt[] = { 4,1,3,5}; 96 if(l <= 2) 97 { 98 if(l == 0 ) 99 printf("Case %d: 1\n",ca);100 if(l == 1 )101 printf("Case %d: 4\n",ca);102 if(l == 2 )103 printf("Case %d: 9\n",ca);104 continue;105 }106 Matrix a;107 a.init();108 a = Pow(a,l - 1);109 //a.output();110 int ans = 0 ; 111 for(int i = 0 ;i < n;i ++)112 {113 ans = (ans + a.mat[3][i] *tt[3-i] )%m ;114 }115 printf("Case %d: %d\n",ca,ans);116 }117 return 0;118 }
转载于:https://www.cnblogs.com/zyue/p/3977892.html
