题解 | #Fibonacci sSum#

思路：

题目的主要信息：

• 斐波那契数列，其中
• 求

方法一：暴力解法（超时）
具体做法：
使用动态规划求斐波那契数列前n项的值，然后三个循环按照公式相加。

class Solution {
public:
    int mod = 1e9 + 7;
    int getSum(int n) {
        vector<int> dp(n + 1, 0); //动态规划求前n个斐波那契数列
        dp[1] = 1;
        for(int i = 2; i <= n; i++) 
            dp[i] = (dp[i - 2] + dp[i - 1]) % mod; //公式相加
        int res = 0;
        for(int i = 1; i <= n; i++) //三层遍历，按照公式
            for(int j = 1; j <= i; j++)
                for(int k = 1; k <= j; k++)
                    res = (res + dp[k]) % mod;
        return res;
    }
};

复杂度分析：

• 时间复杂度：，求所有的斐波那契数列为，最后的公式三层循环
• 空间复杂度：，辅助数组dp记录前项斐波那契数列

方法二：矩阵快速幂
具体做法：
上述做法加得太过于复杂，毕竟这是相当于一个数列相加，我们用数列求和的方式对其化简一下：

得到如上图所示的递推公式以后，我们可以将其换成矩阵写法：

于是我们只需要得到中间那个数字矩阵的次方，然后再与后面一个矩阵相乘，第一个元素即是我们要求的，其中.

为了快速求中间那个矩阵的的次方，我们可以采用矩阵快速幂。参考数字的快速幂 ，矩阵也有类似的算法：

可以使用类似二分的方法来计算矩阵的幂，这样我们只需要计算即可。

class Solution {
public:
    int mod = 1e9 + 7;
    vector<vector<long>> base = { //由刚刚推算出的基础矩阵
        {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>> Mul(vector<vector<long>>& x, vector<vector<long>>& y){ //x矩阵乘上y矩阵
        int n = y[0].size(); //查看第二维是1还是5
        vector<vector<long>> res(5, vector<long>(n, 0));
        for(int i = 0; i < 5; i++){ //遍历相乘相加
            for(int j = 0; j < n; j++){
                for(int k = 0; k < 5; k++){
                    res[i][j] = (res[i][j] + x[i][k] * y[k][j]) % mod; 
                }
            }
        }
        return res;
    }
    vector<vector<long>> Pow(vector<vector<long>>& x, int k){ //矩阵快速幂
        vector<vector<long>> res(5, vector<long>(5, 0));
        for(int i = 0; i < 5; i++)
            res[i][i] = 1; //初始化为单位矩阵
        while(k){
            if(k & 1) 
                res = Mul(res, base);
            k = k >> 1;
            base = Mul(base, base);
        }
        return res;
    }
    int getSum(int n) {
        if(n == 1) //优先判断1和2
            return 1;
        if(n == 2)
            return 4;
        vector<vector<long>> a = base;
        vector<vector<long>> b = {{4},{3},{2},{1},{1}}; 
        vector<vector<long>> c = Pow(a, n - 2); //基础矩阵的n-2次方
        return (int)Mul(c, b)[0][0]; //二者相乘
    }
};

复杂度分析：

• 时间复杂度：，矩阵快速幂一共调用次乘法运算，乘法运算为复杂度为，故总时间复杂度为
• 空间复杂度：，所有辅助矩阵要么是要么就是，属于常数空间