题解 | #Fibonacci sSum#

NC584 Fibonacci sSum

题意

求斐波那契数列数列前n项和的前n项和的前n项和。

1. 暴力法

直接模拟即可。

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    unordered_map<int, int> m;

    const int M = 1e9 + 7;

    int fib(int k) {
        if (m[k]) return m[k]; // 记忆化搜索

        if (k == 1 || k == 2) return 1;

        int res = (fib(k-1) + fib(k-2)) % M;

        m[k] = res;
        return res;
    }
    int getSum(int n) {
        m[1] = 1, m[2] = 1;

        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 + fib(k)) % M;
            }
        }

        return res;
    }
};

• 时间复杂度: ，三重循环套一个fib序列的计算公式，fib的计算通过记忆化搜索可以优化到
• 空间复杂度: ，定义一个长度为的map

2. 矩阵快速幂（正解）

n的范围高达，方法1肯定是错误的，那么我们看下怎么优化。

设斐波那契数列的第i项为，我们令:

表示的前缀和，即：

表示的前缀和，即：

我们要求的就是的前缀和，即：

那么我们要求的答案不就是吗？

我们继续推导：

整理得：

我们可以把上式构造一个矩阵如图所示：

设等号左边的列矩阵为，中间的0-1方阵为，则有：

这就是一个类似等比数列的矩阵关系，稍微推广一下可以得出：

P是已知的，也都是可以直接手算出来的，问题就变成了如何快速求. 朴素的做法是直接乘，但这样的复杂度也达到了,依然不符合要求。

这里用到了一个算法：矩阵快速幂

我们知道，矩阵的乘法和普通乘法一样，也是满足结合律的。因此我们可以使用一种 分治 的思路，把A的n次方拆成规模为的方案：

这样我们就可以逐渐把n以二分的方式降阶，最终实现的时间内计算矩阵的n次幂。

实现中，我们可以对n进行二进制拆分，计算n的每一位二进制位是否有贡献，先贴上模板代码：

//泛型快速算a的n次幂
template <typename T>
T qpow(T a, ll n)
{
    T ans = E; // 赋值为乘法单位元，对于T是矩阵，赋值为单位矩阵
    while (n)
    {
        if (n & 1)
            ans = ans * a;
        n >>= 1;
        a = a * a;
    }
    return ans;
}

以计算为例， 演示上述代码的执行流程：

如上所述，我们把20次乘法优化到5次乘法。这样我们将一个的算法逐步优化到, 这道题就可以过了。

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */

    using ll = long long;
    using vll = vector<ll>;
    using mat = vector<vll>; // 定义矩阵

    const int M = 1e9 + 7;

    mat E;

    // 朴素的矩阵乘法, 直接算就可以了
    mat mul(mat &A, mat &B) {
        mat res(5, vll(5, 0));
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    ll &p = res[i][j];
                    p += A[i][k] * B[k][j];
                    p %= M;
                }
            }
        }
        return res;
    }
    // 矩阵快速幂
    mat qpow(mat A, ll n) {
        mat ans(E); // 初始化为单位矩阵，n=0时直接返回E

        while (n) {
            if (n&1) 
                ans = mul(ans, A);
            n >>= 1;
            A = mul(A, A);
        }

        return ans;
    }
    int getSum(int n) {
        E.resize(5, vll(5, 0));
        for (int i = 0; i < 5; i++)
            E[i][i] = 1;

        // p是上面证明出来的
        mat p = {
            {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}
        };

        // 算P的n-1次方
        p = qpow(p, n-1);

        // A1是(1,1,1,1,0) 直接手算出来的
        // p的n-1次方已经知道了，算出res就可以了
        ll res = 0;
        for (int i = 0; i < 4; i++)
            res += p[0][i];

        return res % M;
    }
};

• 时间复杂度: ，矩阵快速幂的复杂度是, 朴素的m阶矩阵乘法复杂度是, 本题的，是个常数。
• 空间复杂度: ，定义了阶数为5的矩阵，也视为常数。