题解 | #Fibonacci sSum#

题意：

f(n)是Fibonacci数列.
求F(n)%1000000007的值.

方法一：

暴力枚举

思路：记忆化搜索Fibonacci数列，用map存储Fibonacci数列。

三重循环模拟累加。

class Solution {
public:
    /**
     *
     * @param n int整型
     * @return int整型
     */
    int MOD=1e9+7;
    map<int,int> f;//存储fibonacci
    int fibonacci(int x)//递归 O（n） 记忆化搜索
    {
        if(f[x])
            return f[x];
        if(x==1||x==2)
            return 1;
        return f[x]=(fibonacci(x-1)+fibonacci(x-2))%MOD;
    }
    int getSum(int n) {
        int ans=0;

        for(int i=1;i<=n;i++)//三重循环
        {
            for(int j=1;j<=i;j++)
            {
                for(int k=1;k<=j;k++)
                {
                    ans=(ans+fibonacci(k))%MOD;
                }
            }
        }
        return ans;
    }
};

时间复杂度: $图片说明$ ，n是 $图片说明$ ，所以肯定超时。

空间复杂度： $图片说明$ ,n是map存储的大小和递归栈的深度。

方法二：

矩阵快速幂

思路：

已知f(i)是fibonacci数列，设g(i)是f(i)的前i项和，h(i)是g(i)的前i项和，F(i)是h(i)的前i项和。

因而我们可以按照以下推导：

$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); \\ f(n-1)=f(n-1);$

根据线性代数，可以得到矩阵乘法：

$图片说明$

设推理得到的方阵为S，则 $图片说明$ 。

$图片说明$

所以 $图片说明$ 。

$图片说明$ 。

先从整数的快速幂算法讲起，

$图片说明$ ,同理，我们的矩阵快速幂 $图片说明$ 也可以按照将指数n拆分为二进制。

class Solution {
public:
    
    int MOD=1e9+7;
    vector<vector<long>> s={//公式推导出的s矩阵
        {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>> init_matrix={{4},{3},{2},{1},{1}};//n=2时的初始化矩阵A2
    int getSum(int n) {
        if(n==1)
            return 1;
        if(n==2)
            return 4;
        return mul(quickPow(s,n-2),init_matrix)[0][0]%MOD;//先算出S的(n-2)次方，再与A2矩阵相乘

    }

    vector<vector<long>> mul(vector<vector<long>> a,vector<vector<long>> b)//矩阵乘法
    {
        int num = b[0].size();
        vector<vector<long>> c(5,vector<long>(num,0));
        for(int i=0;i<5;i++)
        {
            for(int j=0;j<num;j++)
            {
                for(int k=0;k<5;k++)
                {
                    c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;//矩阵相乘公式
                }
            }
        }
        return c;
    }

    vector<vector<long>> quickPow(vector<vector<long>> x,int n)//矩阵x的n次幂
    {
        vector<vector<long>> ans(5,vector<long>(5,0));
        for(int i=0;i<5;i++)//初始化成单位矩阵
            ans[i][i]=1;
        while(n)
        {
            if(n&1)
            {
                ans=mul(ans,x);//如果该二进制位为1，则乘上该项
            }
            x=mul(x,x);//自乘
            n>>=1;//右移一位
        }
        return ans;
    }
};

时间复杂度： $图片说明$ ，矩阵的n次方，n是指数，拆分为二进制。

空间复杂度： $图片说明$ ，存储的都是常数级别的矩阵。