又见斐波拉契（矩阵快速幂）

描述

传送门：2018年湘潭大学程序设计竞赛-G

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

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

给定递推式
求F(n)的值，由于这个值可能太大，请对$10^9+7$取模。

Input

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

Output

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

Examples

• intput

  4
  1
  2
  3
  100

• output

  1
  16
  57
  558616258

思路

• n最大$10^18$，O(n)肯定会T，可以考虑矩阵快速幂求解。
• 由于题目给了递推式，所以很显然我们需要求一个$X$矩阵，使得这个矩阵满足
  $\begin{equation*} X^{i - 1} \begin{bmatrix} F_{1}\\ F_0\\ 1\\ 1\\ 1\\ 1 \end{bmatrix}= X \begin{bmatrix} F_{i - 1}\\ F_{i - 2}\\ i^3\\ i^2\\ i\\ 1 \end{bmatrix}= \begin{bmatrix} F_{i}\\ F_{i - 1}\\ (i + 1)^3\\ (i + 1)^2\\ i + 1\\ 1 \end{bmatrix} \end{equation*}$，易得$X=\begin{bmatrix} 1&1&1&1&1&1\\ 1 & 0&0&0&0&0\\ 0 & 0&1&3&3&1\\ 0 & 0&0&1&2&1\\ 0 & 0&0&0&1&1\\ 0 & 0&0&0&0&1\\ \end{bmatrix}$。
  将$F_{i}，F_{i - 1}，(i + 1)^3，(i + 1)^2$按递推式展开，取对应系数即可，
• 递推式是从2开始的，所以对与第$n$项，只需求$X^{n-1}$，所得矩阵再左乘一个$\begin{bmatrix}F_1 & F_0 & 2^3 & 2^2 & 2 & 1\end{bmatrix}^{-1}$，所得矩阵的第一个元素即为$F_i$

代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
typedef long long ll;
const ll mod= 1e9+7;

struct Mat{     //矩阵
    ll data[6][6];
    Mat(){CRL(data,0);}
    Mat operator* (Mat &a) const{       //重载*运算符
        Mat c;
        rep(i,0,6)
            rep(j,0,6)
                rep(k,0,6)
                    c.data[i][j]=(c.data[i][j]+data[i][k]*a.data[k][j]%mod)%mod;
        return c;
    }
};

Mat Mat_qpow(Mat a,ll n){   //矩阵快速幂
    Mat tem;rep(i,0,6) tem.data[i][i]=1;    //单位阵初始化
    while(n){
        if(n&1) tem=tem*a;
        a=a*a;
        n>>=1;
    }
    return tem;
}

ll M[6][6] = {      //常数阵，即上面提到的X矩阵
    {1, 1, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 0},
    {0, 0, 1, 3, 3, 1},
    {0, 0, 0, 1, 2, 1},
    {0, 0, 0, 0, 1, 1},
    {0, 0, 0, 0, 0, 1}
};

int main()
{
    Mat a,ans;
    memcpy(a.data,M,sizeof(M));
    int t;ll n;
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&n);
        if(n<2LL) {printf("%lld\n",n);continue;}//特判
        ans=Mat_qpow(a,n-1);
        printf("%lld\n",(ans.data[0][0]+ans.data[0][2]*8%mod+ans.data[0][3]*4%mod+ans.data[0][4]*2%mod+ans.data[0][5])%mod);
    }
    return 0;
}