首页 > 试题广场 >

Fibonacci sSum

[编程题]Fibonacci sSum
  • 热度指数:1814 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
已知Fibonacci数列f(n) ,
给定 ,
求 F(n) % 1000000007的值
示例1

输入

1

输出

1

说明

F(1) = f(1) = 1 
示例2

输入

2

输出

4
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    const int M = 1e9+7;
    vector<vector<long>> D = {{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>> matmul(vector<vector<long>> A, vector<vector<long>> B){
        int n=A.size(), m=B[0].size(), p=B.size();
        vector<vector<long>> C(n, vector<long>(p));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                for(int k=0;k<p;k++)
                    C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % M;
        return C;
    }
    vector<vector<long>> pow(vector<vector<long>> A, int k){
        int n=A.size();
        vector<vector<long>> R(n, vector<long>(n)), B=A;
        for(int i=0;i<n;i++)
            R[i][i] = 1;
        while(k){
            if(k&1)
                R = matmul(R, B);
            B = matmul(B, B);
            k>>=1;
        }
        return R;
    }
    int getSum(int n) {
        if(n==1)
            return 1;
        if(n==2)
            return 4;
        vector<vector<long>> A=D, X(5, vector<long>(1));
        X[0][0] = 4;
        X[1][0] = 3;
        X[2][0] = 2;
        X[3][0] = X[4][0] = 1;
        vector<vector<long>> T = pow(A, n-2);
        vector<vector<long>> R = matmul(T, X);
        return R[0][0];
    }
};

发表于 2020-09-04 16:37:56 回复(0)

设g[j] = f[1] + f[2] + ... + f[j],h[i] = g[1] + g[2] + ... + g[i]。
因此g[j] = g[j-1] + f[j],h[i] = h[i-1] + g[i]。
那么F[n] = h[1] + h[2] + ... + h[n] = F[n-1] + h[n] = F[n-1] + h[n-1] + g[n] = F[n-1] + h[n-1] + g[n-1] + f[n] = F[n-1] + h[n-1] + g[n-1] + f[n-1] + f[n-2]。
因此我们得到递推式F[n] = F[n-1] + h[n-1] + g[n-1] + f[n-1] + f[n-2]。根据此递推式可构造矩阵相乘。

直接上矩阵快速幂即可,复杂度O(5^3logn)=O(125logn)。注意n=1和n=2时特判下即可。

#define ll long long
#define mat vector<vector<ll>>
const int Mod = 1e9+7;
ll base[5][5] = {
        {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}
};
class Solution {
public:
    mat matMul(mat& a,mat& b){
        int n = a.size(), m = b.size(), p = b[0].size();
        mat c(n,vector(p));
        for(int i=0;i<n;i++){
            for(int j=0;j<p;j++){
                for(int k=0;k<m;k++){
                    c[i][j] +=a[i][k] * b[k][j];
                    c[i][j]%=Mod;
                }
            }
        }
        return c;
    }
    mat pow(mat& a,int k){
        int n = a.size();
        mat res(n,vector(n));
        for(int i=0;i<n;i++) res[i][i] = 1;
        mat base = a;
        while(k){
            if(k&1) res = matMul(res,base);
            k>>=1;
            base = matMul(base,base);
        }
        return res;
    }
    /**
     *
     * @param n int整型
     * @return int整型
     */
    int getSum(int n) {
        // write code here
        if(n==1) return 1;
        if(n==2) return 4;
        mat a(5,vector(5));
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++) a[i][j] = base[i][j];
        }
        mat b(5,vector(1));
        b[0][0] = 4,b[1][0] = 3, b[2][0] = 2, b[3][0] = b[4][0] = 1;
        mat tmp = pow(a,n-2);
        mat res = matMul(tmp,b);
        return res[0][0];
    }
};
编辑于 2020-04-23 19:42:00 回复(2)
利用四个dp数组保存累加和的状态,dpk[k]表示f(k) 从i=1,到i=k的菲薄垃圾数列累加和
只通过了80%的示例,请大佬指点一下
public int getSum (int n) {
        // write code here
        int sum=0;
        int[] dp=new int[n+1];
        int[] dpk=new int[n+1];
        int[] dpj=new int[n+1];
        int[] dpi=new int[n+1];
        dp[1]=1;
        for(int i=2;i<n+1;i++){
            dp[i]=dp[i-1]+dp[i-2];
            dp[i]%=1000000007;
        }
        for(int k=1;k<=n;k++){
            dpk[k]+=dpk[k-1]+dp[k];
            dpk[k]%=1000000007;
        }
        for(int k=1;k<=n;k++){
            dpj[k]+=dpj[k-1]+dpk[k];
            dpj[k]%=1000000007;
        }
        for(int k=1;k<=n;k++){
            dpi[k]+=dpi[k-1]+dpj[k];
            dpi[k]%=1000000007;
        }
        return dpi[n];
    }
发表于 2020-07-19 23:01:12 回复(0)
        if(n > 1e8) return n; 
为啥要加这么一行代码,,好奇怪。
发表于 2020-07-10 11:14:23 回复(1)

问题信息

难度:
4条回答 3326浏览

热门推荐

通过挑战的用户

查看代码
Fibonacci sSum