题解 | #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;
    }
};

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

2. 矩阵快速幂（正解）

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

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

$g[i]$ 表示 $f[i]$ 的前缀和，即：

$g[n] = \sum_{i=1}^nf[i]$

$h[i]$ 表示 $g[i]$ 的前缀和，即：

$h[n] = \sum_{i=1}^ng[i]$

我们要求的 $F[i]$ 就是 $h[i]$ 的前缀和，即：

$F[n] = \sum_{i=1}^nh[i]$

那么我们要求的答案不就是 $F[n]$ 吗？

我们继续推导：

$F[n] = F[n-1] + h[n] \\ h[n] = h[n-1] + g[n] \\ g[n] = g[n-1] + f[n] \\ f[n] = f[n-1] + f[n-2]$

整理得： $F[n] = F[n-1]+h[n-1]+g[n-1]+f[n-1]+f[n-2] \\ h[n] = h[n-1]+g[n-1]+f[n-1]+f[n-2] \\ g[n] = g[n-1]+f[n-1]+f[n-2] \\ f[n] = f[n-1]+f[n-2]$

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

$\left[ \begin{array}{c} F[n] \\ h[n]\\ g[n] \\ f[n] \\ f[n-1] \end{array} \right] = \left[ \begin{array}{c} 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\\ \end{array} \right] \cdot \left[ \begin{array}{c} F[n-1] \\ h[n-1]\\ g[n-1] \\ f[n-1] \\ f[n-2] \end{array} \right]$

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

$A_n = PA_{n-1}$

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

$A_n = P^{n-1}A_1$

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

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

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

$A^n= \begin{cases} A^{n-1} \cdot A& n为奇数 \\ A^{n/2} \cdot A^{n/2 }& n为偶数\\ E & n为0 \end{cases}$

这样我们就可以逐渐把n以二分的方式降阶，最终实现 $logn$ 的时间内计算矩阵的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;
}

以计算 $A^{20}$ 为例，演示上述代码的执行流程：

图片说明

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

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;
    }
};

时间复杂度: $O(logn)$ ，矩阵快速幂的复杂度是 $logn$ , 朴素的m阶矩阵乘法复杂度是 $O(m^3)$ , 本题的 $m=5$ ，是个常数。
空间复杂度: $O(1)$ ，定义了阶数为5的矩阵，也视为常数。