又见斐波那契~矩阵快速幂入门题

链接：https://www.nowcoder.com/acm/contest/105/G
来源：牛客网

题目描述

这是一个加强版的斐波那契数列。

给定递推式 $F(i) = \left\{ \begin{array} \\F(i-1) + F(i-2) + i^3 + i^2 + i + 1 & i>1 \\0 & i = 0 \\1 & i = 1\end{array}\right.$

求F(n)的值，由于这个值可能太大，请对10⁹+7取模。

输入描述:

第一行是一个整数T(1 ≤ T ≤ 1000)，表示样例的个数。
以后每个样例一行，是一个整数n(1 ≤ n ≤ 10

¹⁸

)。

输出描述:

每个样例输出一行，一个整数，表示F(n) mod 1000000007。

示例1

输入

输出

1
16
57
558616258

这题是一题矩阵快速幂的模板题，表示第一次碰到矩阵快速幂然后就顺便学一下，其实和快速幂差不多。
矩阵快速幂的难点一般是构造矩阵，但是这题递推公式给了我们还是非常容易构造出矩阵的。
难题一般都是让我们自己去推公式，然后再通过公式写出所需要的矩阵。

$F(i) = \left\{ \begin{array} \\F(i-1) + F(i-2) + i^3 + i^2 + i + 1 & i>1 \\0 & i = 0 \\1 & i = 1\end{array}\right.$

递推公式给了我们，
就是要找到一个矩阵A 【f(i),f(i-1),(i+1)^3,(i+1)^2,(i+1),1】 * A =【f(i-1),f(i-2),i^3,i^2,i,1】;
如果学过线代，这个是非常容易推出来的。
然后就通过矩阵的性质，   F【n】=A^(n-1)*F【1】;
知道这些，就会发现这不就是一个SB题吗

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <vector>
 4 #include <queue>
 5 #include <cstring>
 6 #include <string>
 7 using namespace std;
 8 const int maxn = 1e2 + 10;
 9 const int mod = 1e9 + 7;
10 typedef long long LL ;
11 struct mat
12 {
13     LL m[maxn][maxn];
14     mat() {
15        memset(m,0,sizeof(m));
16     }
17     mat operator * (mat &a ) {
18        mat ans;
19        for (int i=0 ;i<6 ;i++  ){
20           for (int j=0 ;j<6 ;j++) {
21               for (int k=0 ;k<6 ;k++) {
22                  ans.m[i][j]=(ans.m[i][j]+m[i][k]*a.m[k][j])%mod;
23               }
24           }
25        }
26        return ans;
27     }
28 };
29 mat modexp(mat a,LL b)
30 {
31     mat ans;
32     for (int i=0 ;i<6 ;i++ ) ans.m[i][i]=1;
33     while(b) {
34         if (b&1) ans=ans*a;
35         b=b>>1;
36         a=a*a;
37     }
38     return ans;
39 }
40 int main() {
41     long long  mm[6][6] = {
42         {1, 1, 1, 1, 1, 1},
43         {1, 0, 0, 0, 0, 0},
44         {0, 0, 1, 3, 3, 1},
45         {0, 0, 0, 1, 2, 1},
46         {0, 0, 0, 0, 1, 1},
47         {0, 0, 0, 0, 0, 1}
48     };
49     int t;
50     scanf("%d", &t);
51     while(t--) {
52         LL  n;
53         mat ans;
54         for (int i = 0 ; i < 6 ; i++) {
55             for (int j = 0 ; j < 6 ; j++) {
56                 ans.m[i][j] = mm[i][j];
57             }
58         }
59         scanf("%lld", &n);
60         ans = modexp(ans, n - 1);
61         printf("%lld
", (ans.m[0][0] + ans.m[0][2] * 8 + ans.m[0][3] * 4 + ans.m[0][4] * 2 + ans.m[0][5]) % mod);
62     }
63     return 0;
64 }