牛牛的Fib序列

描述
牛牛重新定义了斐波那契数列，牛牛定义f(n) = f(n-1)+f(n+1); f(1)=a, f(2)=b， 现在给定初始值 a, b，现在求第n项f(n)%1000000007的值。其中 1<=|x|, |y|, n<=10^9 
示例
输入：1,2,3
返回值：1
说明：f(2)=f(3)+f(1), 所以f(3) = f(2)-f(1)=2-1=1

方法一

思路分析

首先我们可以根据常规解法，利用求解斐波那契数列的思想求解本题，不过首先需要根据题目中所给的推导公式，从而得出函数的推导公式，推导过程如下：

根据推导公式得到函数的递推公式，根据递推公式写出代码。不过由于超出内存限制无法通过

核心代码 

#
# 
# @param a int整型 
# @param b int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def solve(self, a, b, n):
        mod=1000000007
        array=[0 for i in range(n)]
        array[0]=a;
        array[1]=b;
        for i in range(2,n):
            array[i]=array[i-1]-array[i-2]
        return array[n%6-1]%mod
复杂度分析
  • 时间复杂度：时间复杂度为$O(n)$
  • 空间复杂度：空间上需要的额外空间$O(n)$

方法二

思路分析

通过推到可以得到所给的函数是一个周期函数，具体的推导过程如下。

图解+推导过程



核心代码 

#
# 
# @param a int整型 
# @param b int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def solve(self, a, b, n):
        array=[a,b,b-a,-a,-b,a-b]
        return array[n%6-1]%1000000007

复杂度分析

  • 时间复杂度：由题目可推导出函数是一个周期函数，因此在常数时间内计算得到周期内的函数结果，总的时间复杂度为$O(1)$
  • 空间复杂度：使用的额外空间为常数级的$O(1)$