WHU 1540 Fibonacci 递推

武大邀请赛的网络预选赛，就去做了个签到题，居然连这个递推都没推出来，真是惭愧。

而且好久没写矩阵乘法了，来回顾一下。

题意：

　　求Fibonacci数列的，前n项立方和。

思路：

　　可以求得一下递推公式：

然后用矩阵快速幂求出结果即可。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <functional>
 5 
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 
10 const ll MOD  = (ll)1e9+7;
11 const ll ONE[][5] = {
12     {1, 0, 0, 0, 0},
13     {0, 1, 0, 0, 0},
14     {0, 0, 1, 0, 0},
15     {0, 0, 0, 1, 0},
16     {0, 0, 0, 0, 1},
17 };
18 const ll MU[][5] = {
19     {0, 0, 0, 1, 0},
20     {0, 0, 1, 1, 0},
21     {0, 1, 2, 1, 0},
22     {1, 3, 3, 1, 0},
23     {1, 3, 3, 1, 1},
24 };
25 const ll v1[5] = {1, 1, 1, 1, 2};
26 struct Matrix {
27     ll body[5][5];
28 
29     Matrix() {}
30     Matrix(bool x) {
31         if (x) {
32             for (int i = 0; i < 5; i++)
33                 for (int j = 0; j < 5; j++)
34                     body[i][j] = ONE[i][j];
35         } else {
36             for (int i = 0; i < 5; i++)
37                 for (int j = 0; j < 5; j++)
38                     body[i][j] = MU[i][j];
39         }
40     }
41 
42     Matrix operator * (const Matrix &x) {
43         Matrix res;
44         ll tmp = 0;
45         for (int i = 0; i < 5; i++)
46             for (int j = 0; j < 5; j++) {
47                 tmp = 0;
48                 for (int k = 0; k < 5; k++)
49                     tmp = (tmp+(body[i][k]*x.body[k][j])%MOD)%MOD;
50                 res.body[i][j] = tmp;
51             }
52         return res;
53     }
54 };
55 
56 Matrix pow(int k){
57     Matrix res(true);
58     Matrix d(false);
59     while (k>0) {
60         if (k&1) res = res*d;
61         d = d*d;
62         k >>= 1;
63     }
64     return res;
65 }
66 
67 int n;
68 ll v2[5];
69 
70 int main() {
71     #ifdef Phantom01
72         freopen("WHU1540.txt", "r", stdin);
73     #endif // Phantom01
74 
75     while (scanf("%d", &n)!=EOF) {
76         if (0==n) break;
77 
78         if (n<=2) {
79             printf("%d
", n);
80             continue;
81         }
82         Matrix tmp = pow(n-2);
83         ll t = 0;
84         for (int i = 0; i < 5; i++) {
85             t = 0;
86             for (int j = 0; j < 5; j++)
87                 t = (t+(tmp.body[i][j]*v1[j])%MOD)%MOD;
88             v2[i] = t;
89         }
90         printf("%d
", (int)v2[4]);
91     }
92 
93     return 0;
94 }