描述

这是一篇面对初级coder的题解。

知识点：数学 递推

难度：五星

题解

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

分析： 斐波那契数列本身就有一定的递推特性，需要结合数学知识递推求得

方法一 递推：

已知$f\left(n\right)=f(n-1)+f(n-2)f(n)=f(n-1)+f(n-2)$f(n)=f(n−1)+f(n−2)

设$T\left(n\right)={\sum }_{i=1}^{n}f\left(i\right)T(n)=\backslash sum\_\{i=1\}^nf(i)$T(n)=∑i=1n​f(i)有$T\left(n\right)=T(n-1)+f\left(n\right)T(n)=T(n-1)+f(n)$T(n)=T(n−1)+f(n)

设$G\left(n\right)={\sum }_{i=1}^{n}T\left(i\right)G(n)=\backslash sum\_\{i=1\}^nT(i)$G(n)=∑i=1n​T(i)有$G\left(n\right)=G(n-1)+T\left(n\right)G(n)=G(n-1)+T(n)$G(n)=G(n−1)+T(n)

设$F\left(n\right)={\sum }_{i=1}^{n}G\left(i\right)F(n)=\backslash sum\_\{i=1\}^nG(i)$F(n)=∑i=1n​G(i)有$F\left(n\right)=F(n-1)+G\left(n\right)F(n)=F(n-1)+G(n)$F(n)=F(n−1)+G(n)

$F\left(n\right)F(n)$F(n) 即为所求 这样的话就优化了递推的式子。

class Solution {
public:
    const int mod=1e9+7;
    int getSum(int n) {
        /*初始值*/
        int f[3]={0,1,1};//斐波那契数列
        int T=1;//f前n项和T
        int G=1;//T前n项和G
        int F=1;//G前n项和F——所求
        for(int i=2;i<=n;i++){
            f[2]=(f[1]+f[0])%mod;//f(n)=f(n-1)+f(n-2)=1
            f[0]=f[1];//f(n-2)=f(n-1)
            f[1]=f[2];//f(n-1)=f(n)
            T=(T+f[2])%mod;//T(n)=T(n-1)+f(n)
            G=(G+T)%mod;//G(n)=G(n-1)+T(n)
            F=(F+G)%mod;//F(n)=F(n-1)+G(n)
        }
        return F;
    }
};

运行测试：

9/10 组用例通过 运行时间 1001ms 占用内存 432KB

复杂度分析：

采用递归和记忆化搜索的方式，避免了4重循环

故时间复杂度为$O\left(n\right)O(n)$O(n)——只遍历一遍 空间复杂度为O(1) 仅占用常数空间

方法二 通项公式 递推：

斐波那契数列前n项和：

考虑如下式子

$f(n+2)=f(n+1)+f\left(n\right)f(n+2)=f(n+1)+f(n)$f(n+2)=f(n+1)+f(n)

$f(n+1)=f\left(n\right)+f(n-1)f(n+1)=f(n)+f(n-1)$f(n+1)=f(n)+f(n−1)

$f\left(n\right)=f(n-1)+f(n-2)f(n)=f(n-1)+f(n-2)$f(n)=f(n−1)+f(n−2)

....

$f\left(3\right)=f\left(2\right)+f\left(1\right)f(3)=f(2)+f(1)$f(3)=f(2)+f(1)

对于上面所有式子累加求和有 $f(n+2)={\sum }_{i=1}^{n}f\left(i\right)+f\left(1\right)f(n+2)=\backslash sum\_\{i=1\}^nf(i)+f(1)$f(n+2)=∑i=1n​f(i)+f(1)

即$T\left(n\right)={\sum }_{i=1}^{n}f\left(i\right)=f(n+2)-1T(n)=\backslash sum\_\{i=1\}^nf(i)\; =\; f(n+2)-1$T(n)=∑i=1n​f(i)=f(n+2)−1

同样的$G\left(n\right)={\sum }_{i=1}^{n}T\left(i\right)=T(n+2)-T\left(2\right)-n=f(n+4)-f\left(4\right)-n=f(n+4)-(n+3)G(n)=\backslash sum\_\{i=1\}^nT(i)\; =\; T(n+2)-T(2)-n=f(n+4)-f(4)-n=f(n+4)-(n+3)$G(n)=∑i=1n​T(i)=T(n+2)−T(2)−n=f(n+4)−f(4)−n=f(n+4)−(n+3)

依然类似 $F\left(n\right)={\sum }_{i=1}^{n}G\left(i\right)=T(n+4)-T\left(4\right)-{\sum }_{i=4}^{n}n+3=f(n+6)-f\left(6\right)-(n+7)\ast n/2F(n)=\backslash sum\_\{i=1\}^nG(i)\; =T(n+4)-T(4)-\backslash sum\_\{i=4\}^nn+3=f(n+6)-f(6)-(n+7)*n/2$F(n)=∑i=1n​G(i)=T(n+4)−T(4)−∑i=4n​n+3=f(n+6)−f(6)−(n+7)∗n/2

最后一项是等差数列求和公式且$f\left(6\right)=8f(6)=8$f(6)=8

故所求$F\left(n\right)=f(n+6)-8-(n+7)\ast n/2F(n)=f(n+6)-8-(n+7)*n/2$F(n)=f(n+6)−8−(n+7)∗n/2

通过这样的计算 减少了递推的次数 问题也划归为求斐波那契数列的第n+6项

class Solution {
public:
    const int mod=1e9+7;
    int getSum(int n) {
        /*初始值*/
        int f[3]={0,1,1};//斐波那契数列
        for(int i=2;i<=n+6;i++){
            f[2]=(f[1]+f[0])%mod;//f(n)=f(n-1)+f(n-2)=1
            f[0]=f[1];//f(n-2)=f(n-1)
            f[1]=f[2];//f(n-1)=f(n)
        }
        long long ans=(mod+f[2]-8-(long long)(n+7)*(long long)n/2%mod)%mod;
        return (int) ans;
    }
};

运行测试：

9/10 组用例通过 运行时间 1001ms 占用内存 432KB

复杂度分析：

采用递归和记忆化搜索的方式，避免了4重循环

故时间复杂度为$O\left(n\right)O(n)$O(n)——只遍历一遍

空间复杂度为O(1) 仅占用常数空间

但是仍然超时 说明递推求斐波那契数列的第n+6项仍然耗费过多时间，需要用二分法做进一步优化。

方法三 通项公式 二分法递推：

考虑用数学归纳法证明如下两个关于斐波那契数列的性质

性质一：

若i为奇数， $f\left(i\right)\ast f\left(i\right)=f(i-1)\ast f(i+1)+1f(i)*f(i)=f(i-1)*f(i+1)+1$f(i)∗f(i)=f(i−1)∗f(i+1)+1，否则$f\left(i\right)\ast f\left(i\right)=f(i-1)\ast f(i+1)-1f(i)*f(i)=f(i-1)*f(i+1)-1$f(i)∗f(i)=f(i−1)∗f(i+1)−1

性质二：

$f\left(n\right)=f\left(1\right)\ast f(n-2)+f\left(2\right)\ast f(n-1)=f\left(2\right)\ast f(n-3)+f\left(3\right)\ast f(n-2)=f\left(3\right)\ast f(n-4)+f\left(4\right)\ast f(n-3)=f\left(i\right)\ast f(n-i-1)+f(i+1)\ast f(n-i)f(n)=f(1)*f(n-2)+\; f(2)*f(n-1)\; \backslash \backslash \; =f(2)*f(n-3)+\; f(3)*f(n-2)\; \backslash \backslash \; =f(3)*f(n-4)+\; f(4)*f(n-3)\; \backslash \backslash \; =f(i)*f(n-i-1)+f(i+1)*f(n-i)$f(n)=f(1)∗f(n−2)+f(2)∗f(n−1)=f(2)∗f(n−3)+f(3)∗f(n−2)=f(3)∗f(n−4)+f(4)∗f(n−3)=f(i)∗f(n−i−1)+f(i+1)∗f(n−i)

另$i=n/2i=n/2$i=n/2，可采用二分法用来计算较大的fibonacci数除以某个数的余数，以乘法代替加法，从而将递推复杂度变为$O\left(logn\right)O(logn)$O(logn)

#define max 1000000//测试这个值比较合适 时间短
class Solution {
public:
    const int mod=1e9+7;
    int Fib(int n,vector<int> &f){//二分法计算前n项和
        long long ans;//返回值
        if(n<=max)
            return f[n];//分情况 二分太细乘法复杂度会上升 故先打表
        else{
            int i=n/2;
            //核心二分公式 详见解析 f(n)=f(i)*f(n-i-1)+f(i+1)*f(n-i)
            ans=((long long) Fib(i,f)*(long long) Fib(n-i-1,f)+(long long)Fib(i+1,f)*(long long)Fib(n-i,f))%mod;
        }
        return (int) ans;
    }
    int getSum(int n) {
        vector<int> f(max);//斐波那契数列
        /*初始值*/
        f[0]=0;
        f[1]=1;
        for(int i=2;i<max;i++)//预打表
            f[i]=(f[i-1]+f[i-2])%mod;//f(n)=f(n-1)+f(n-2)=1
        long long ans=(mod+Fib(n+6,f)-8-(long long)(n+7)*(long long)n/2%mod)%mod;//推导公式直接计算
        return (int) ans;
    }
};

运行测试：

通过全部用例 运行时间 21ms 占用内存 4296KB

复杂度分析：

实际测试发现，频繁做小数的乘法耗时长，故定义一个分界值max

小于此值时用递推的结果，大于此值用二分的结果

故时间复杂度为$O\left(logn\right)O(logn)$O(logn)——二分法递推

空间复杂度为O(1) 仅占用常数空间

总结

数学很重要

当n进一步增大时 即$n+6>modn+6>mod$n+6>mod时

考虑斐波那契数列通项公式

与费马小定理

有$f(n+6)\%mod=f(n+6-mod)\%modf(n+6)\; \backslash \%\; mod=f(n+6-mod)\; \backslash \%\; mod$f(n+6)%mod=f(n+6−mod)%mod