2021-10-18 11:52 已编辑 AAAAA Beauty Academy (Peoria) 后端

关注

题解 | #Fibonacci sSum#

Fibonacci sSum

http://www.nowcoder.com/practice/2c212c21da5e44c1a1a0543d975f4d1e

题意：

定义 $\begin{equation} f(n)=\left\{ \begin{aligned} 1 & & n=1,2 \\ f(n-1)+f(n-1) & & n>2 \\ \end{aligned} \right. \end{equation}$ ，求 $\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{j}{f(k)} mod(10^9+7)$

解法一（递推法）

我们设 $T(n)=\sum_{i=1}^nf(i)$ ，显然有 $T(n)=T(n-1)+f(n)$

我们发现 $\sum_{j=1}^i\sum_{k=1}^jf(k)=\sum_{j=1}^iT(j)$ ，那么我们可设 $G(n)=\sum_{i=1}^nT(i)$ ，显然有 $G(n)=G(n-1)+T(n)$

同理我们可得 $\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^jf(k)=\sum_{i=1}^n\sum_{j=1}^iT(j)=\sum_{i=1}^nG(i)$ ，设 $F(n)=\sum_{i=1}^nG(i)$ ，显然有 $F(n)=F(n-1)+G(n)$

于是我们就可以做到用线性复杂度求解本题了。

代码：

class Solution {
public:
    const int mod=1e9+7;
    int f[1000000001];
    int T[1000000001];
    int G[1000000001];
    int F[1000000001];
    int getSum(int n) {
        /*边界值*/
        f[0]=0;
        f[1]=1;
        T[1]=1;
        G[1]=1;
        F[1]=1;
        for(int i=2;i<=n;i++){
            f[i]=(f[i-1]+f[i-2])%mod;//f(2)=f(1)+f(0)=1
            T[i]=(T[i-1]+f[i])%mod;//\sum_{i=1}^nf(i)
            G[i]=(G[i-1]+T[i])%mod;//\sum_{i=1}^nT(i)
            F[i]=(F[i-1]+G[i])%mod;//\sum_{i=1}^nG(i)
        }
        return F[n];
    }
};

时间复杂度： $O(n)$ ，我们需要递推第 $2\sim n$ 项的值，单次递推是 $O(1)$ 的，故总的时间复杂度为 $O(n)$

空间复杂度： $O(n)$ ，数组 $f,T,G,F$ 都是 $O(n)$ 大小的，故总的空间复杂度为 $O(n)$

解法二（矩阵快速幂）

由

$f(n)=f(n-1)+f(n-2)\\ T(n)=T(n-1)+f(n)$

可推出 $T(n)-T(n-1)=T(n-1)-T(n-2)+T(n-2)-T(n-3)$

即： $T(n)=2*T(n-1)-T(n-3)$

由

$T(n)=2*T(n-1)-T(n-3)\\ G(n)=G(n-1)+T(n)$

可推出 $G(n)-G(n-1)=2*(G(n-1)-G(n-2))-(G(n-3)-G(n-4))$

即： $G(n)=3*G(n-1)-2*G(n-2)-G(n-3)+G(n-4)$

由

$G(n)=3*G(n-1)-2*G(n-2)-G(n-3)+G(n-4)\\ F(n)=F(n-1)+G(n)$

可推出 $F(n)-F(n-1)=3*(F(n-1)-F(n-2))-2*(F(n-2)-F(n-3))-(F(n-3)-F(n-4))+F(n-4)-F(n-5)$

即： $F(n)=4*F(n-1)-5*F(n-2)+F(n-3)+2*F(n-4)-F(n-5)$

于是我们可以构造矩阵乘法式子：

$\left[ \begin{matrix} F(n) \\ F(n-1) \\ F(n-2)\\ F(n-3)\\ F(n-4) \end{matrix} \right]=\left[ \begin{matrix} 4 & -5 & 1 & 2 & -1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 \end{matrix} \right]*\left[ \begin{matrix} F(n-1) \\ F(n-2) \\ F(n-3)\\ F(n-4)\\ F(n-5) \end{matrix} \right]$

于是有

$\left[ \begin{matrix} F(n) \\ F(n-1) \\ F(n-2)\\ F(n-3)\\ F(n-4) \end{matrix} \right]=\left[ \begin{matrix} 4 & -5 & 1 & 2 & -1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 \end{matrix} \right]^{n-5}*\left[ \begin{matrix} F(5) \\ F(4) \\ F(3)\\ F(2)\\ F(1) \end{matrix} \right]$

我们就可以利用矩阵快速幂算法求解了。

具体的，为了方便起见，我们 $F(1)\sim F(5)$ 可以直接三重循环暴力求解（由于数值较小，对应的时间复杂度可视为常数）。

代码：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    static const int mod=1e9+7;
    struct mat{
        int A[5][5];
        inline mat(){
            memset(A,0,sizeof A);
        }
        inline int* operator [] (int p){
            return A[p];
        }
        inline mat operator * (const mat& other)const{
            mat ret;
            for(int i=0;i<5;i++){
                for(int j=0;j<5;j++){
                    for(int k=0;k<5;k++){
                        //矩阵乘法
                        ret.A[i][j]=(ret.A[i][j]+1ll*A[i][k]*other.A[k][j]%mod)%mod;
                    }
                }
            }
            return ret;
        }
    };
    mat ksm(mat a,int b){
        //矩阵快速幂
        mat ret;
        for(int i=0;i<5;i++)ret.A[i][i]=1;//单位矩阵
        while(b){
            if(b&1){
                ret=ret*a;
            }
            a=a*a;
            b>>=1;
        }
        return ret;
    }
    int f[6];
    int F[6];
    int getSum(int n) {
        f[0]=0,f[1]=1;
        for(int i=2;i<=5;i++){
            f[i]=(f[i-1]+f[i-2])%mod;
        }
        memset(F,0,sizeof F);
        for(int p=1;p<=5;p++){
            for(int i=1;i<=p;i++){
                for(int j=1;j<=i;j++){
                    for(int k=1;k<=j;k++){
                        F[p]=(F[p]+f[k])%mod;//前5个直接暴力求解
                    }
                }
            }
        }
        if(n<=5)return F[n];
        mat t;
        t[0][0]=4,t[0][1]=(-5+mod)%mod,t[0][2]=1,t[0][3]=2,t[0][4]=(-1+mod)%mod;
        t[1][0]=1,t[2][1]=1,t[3][2]=1,t[4][3]=1;//初始化矩阵
        t=ksm(t,n-5);
        int ans=0;
        for(int i=0;i<5;i++){
            ans=(ans+1ll*t[0][i]*F[5-i]%mod)%mod;//模拟矩阵乘法求解答案
        }
        return ans;
    }
};