题解 | #牛牛的Fib序列#

题意整理

• 牛牛定义了满足的一个序列，并且。
• 求序列的第n项。

方法一（数学+dp存状态）

1.解题思路

根据给定的递推关系式，可以得出序列是一个周期为6的循环序列。
证明：

由（记为式子1）可知：（记为式子2），将式子2代入式子1，可得：，同时前移三位，可以推出，于是有：，所以是一个周期为6的序列。

因为是一个周期为6的循环序列，所以只需要计算出余数为0，1，2，3，4，5对应的值即可。然后用一个dp数组存储对应的状态。

动图展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return int整型
     */
    int mod=1000000007;
    public int solve (int a, int b, int n) {
        //定义dp数组
        int[] dp=new int[7];
        //初始化余数为1、2时的值
        dp[1]=(a+mod)%mod;
        dp[2]=(b+mod)%mod;
        //根据递归关系计算余数为3、4、5、0时的值
        for(int i=3;i<=6;i++){
            dp[i]=(dp[i-1]-dp[i-2]+mod)%mod;
        }
        dp[0]=dp[6];
        //周期为6，所以返回对6取余对应的值即可
        return dp[n%6];
    }
}

3.复杂度分析

• 时间复杂度：运算次数是常数级别的，所以时间复杂度是。
• 空间复杂度：需要额外常数级别的存储空间，所以空间复杂度是。

方法二（数学）

1.解题思路

可以直接计算出对应的6种状态值。如果结果小于0，则需要补取余常数，将其变为正数。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return int整型
     */
    //取余常数
    int mod=1000000007;
    public int solve (int a, int b, int n) {
        //初始化结果
        int res=0;
        switch(n%6){
            //余数为1的情形
            case 1:
                res=a%mod;
                break;
            //余数为2的情形
            case 2:
                res=b%mod;
                break;
            //余数为3的情形
            case 3:
                res=(b-a)%mod;
                break;
            //余数为4的情形
            case 4:
                res=(-a)%mod;
                break;
            //余数为5的情形
            case 5:
                res=(-b)%mod;
                break;
            //余数为0的情形
            case 0:
                res=(a-b)%mod;
                break;
        }
        //如果小于0，用mod补齐到正数
        while(res<0){
            res+=mod;
        }   
        return res;
    }
}

3.复杂度分析

• 时间复杂度：运算次数是常数级别的，所以时间复杂度是。
• 空间复杂度：需要额外常数级别的存储空间，所以空间复杂度是。