Fibonacci sSum

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    const int M = 1e9+7;
    vector<vector<long>> D = {{1, 1, 1, 1, 1}, 
                            {0, 1, 1, 1, 1}, 
                            {0, 0, 1, 1, 1},
                            {0, 0, 0, 1, 1}, 
                            {0, 0, 0, 1, 0}};
    vector<vector<long>> matmul(vector<vector<long>> A, vector<vector<long>> B){
        int n=A.size(), m=B[0].size(), p=B.size();
        vector<vector<long>> C(n, vector<long>(p));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                for(int k=0;k<p;k++)
                    C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % M;
        return C;
    }
    vector<vector<long>> pow(vector<vector<long>> A, int k){
        int n=A.size();
        vector<vector<long>> R(n, vector<long>(n)), B=A;
        for(int i=0;i<n;i++)
            R[i][i] = 1;
        while(k){
            if(k&1)
                R = matmul(R, B);
            B = matmul(B, B);
            k>>=1;
        }
        return R;
    }
    int getSum(int n) {
        if(n==1)
            return 1;
        if(n==2)
            return 4;
        vector<vector<long>> A=D, X(5, vector<long>(1));
        X[0][0] = 4;
        X[1][0] = 3;
        X[2][0] = 2;
        X[3][0] = X[4][0] = 1;
        vector<vector<long>> T = pow(A, n-2);
        vector<vector<long>> R = matmul(T, X);
        return R[0][0];
    }
};

设g[j] = f[1] + f[2] + ... + f[j]，h[i] = g[1] + g[2] + ... + g[i]。
因此g[j] = g[j-1] + f[j]，h[i] = h[i-1] + g[i]。
那么F[n] = h[1] + h[2] + ... + h[n] = F[n-1] + h[n] = F[n-1] + h[n-1] + g[n] = F[n-1] + h[n-1] + g[n-1] + f[n] = F[n-1] + h[n-1] + g[n-1] + f[n-1] + f[n-2]。
因此我们得到递推式F[n] = F[n-1] + h[n-1] + g[n-1] + f[n-1] + f[n-2]。根据此递推式可构造矩阵相乘。

直接上矩阵快速幂即可，复杂度O(5^3logn)=O(125logn)。注意n=1和n=2时特判下即可。

#define ll long long
#define mat vector<vector<ll>>
const int Mod = 1e9+7;
ll base[5][5] = {
        {1,1,1,1,1},
        {0,1,1,1,1},
        {0,0,1,1,1},
        {0,0,0,1,1},
        {0,0,0,1,0}
};
class Solution {
public:
    mat matMul(mat& a,mat& b){
        int n = a.size(), m = b.size(), p = b[0].size();
        mat c(n,vector(p));
        for(int i=0;i<n;i++){
            for(int j=0;j<p;j++){
                for(int k=0;k<m;k++){
                    c[i][j] +=a[i][k] * b[k][j];
                    c[i][j]%=Mod;
                }
            }
        }
        return c;
    }
    mat pow(mat& a,int k){
        int n = a.size();
        mat res(n,vector(n));
        for(int i=0;i<n;i++) res[i][i] = 1;
        mat base = a;
        while(k){
            if(k&1) res = matMul(res,base);
            k>>=1;
            base = matMul(base,base);
        }
        return res;
    }
    /**
     *
     * @param n int整型
     * @return int整型
     */
    int getSum(int n) {
        // write code here
        if(n==1) return 1;
        if(n==2) return 4;
        mat a(5,vector(5));
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++) a[i][j] = base[i][j];
        }
        mat b(5,vector(1));
        b[0][0] = 4,b[1][0] = 3, b[2][0] = 2, b[3][0] = b[4][0] = 1;
        mat tmp = pow(a,n-2);
        mat res = matMul(tmp,b);
        return res[0][0];
    }
};