Fibonacci's Sum 解题报告

其实对于这个题目来说，我们可以简单想到矩阵快速幂，那么就根据这个思路往下想，那么我们写出

我们令 ,那么写出的递推式：
我们在令 ,那么写出的递推式：
所以，将式(3)带入式(2)得到：
一步步回代到式(1)，最终 的递推式为：
那么就有：
其中 为 的矩阵，那么矩阵 如下：

将式(4)变为下述式子：
那么最终的
其中 为 矩阵 计算后的结果。

typedef long long LL;
const LL MOD = 1e9+7;
struct Matrix {
    LL mat[5][5];
};
Matrix Multi(Matrix A, Matrix B) {
    Matrix C;
    for(int i=0; i<5; i++) {
        for(int j=0; j<5; j++) {
            C.mat[i][j] = 0;
            for(int k=0; k<5; k++) C.mat[i][j] = (C.mat[i][j]+A.mat[i][k]*B.mat[k][j]%MOD)%MOD;
        }
    }
    return C;
}
Matrix Pow(Matrix A, LL b) {
    Matrix ans;
    memset(ans.mat, 0, sizeof ans.mat);
    for(int i=0; i<5; i++) ans.mat[i][i] = 1;
    while(b) {
        if(b&1) ans=Multi(ans, A);
        b>>=1;
        A = Multi(A, A);
    }
    return ans;
}
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    int getSum(int n) {
        // write code here
        Matrix tmp;
        memset(tmp.mat, 0, sizeof tmp.mat);
        tmp.mat[0][0] = tmp.mat[1][0] = tmp.mat[2][0] = tmp.mat[3][0] = 1;
        tmp.mat[1][1] = tmp.mat[2][1] = tmp.mat[3][1] =  1;
        tmp.mat[2][2] = tmp.mat[3][2] = 1;
        tmp.mat[3][3] = tmp.mat[4][3] = 1;
        tmp.mat[3][4] = 1;
        tmp = Pow(tmp, n-1);
        LL ans=tmp.mat[0][0]+tmp.mat[1][0]+tmp.mat[2][0]+tmp.mat[3][0]+tmp.mat[4][0];
        ans = (ans%MOD+MOD)%MOD;
        return ans;
    }
};