题解 | #数列求值#

题意整理

已知数列第0项为0，第1项为1，递推关系为： $a_i=b*a_{i-1}+c*a_{i-2}(i>=2)$ 。
求数列第n项，结果需要对1000000007取余。

方法一（暴力）

1.解题思路

首先处理第0项和第1项的结果。
用变量x、y分别记录数列第i-2项和第i-1项。
循环对应次数，按递推关系式跟新每次的结果，同时将x换为y，y换为计算出的结果。

测试数据较大时，运行超时。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 输出序列的第n项
     * @param n long长整型 序列的项数
     * @param b long长整型 系数
     * @param c long长整型 系数
     * @return long长整型
     */
    //取余常数
    int mod=1000000007;
    public long nthElement (long n, long b, long c) {
        //特殊情况处理
        if(n==0) return 0;
        if(n==1) return 1;
        //结果变量
        long res=0L;
        //记录第i-2项
        long x=0L;
        //记录第i-1项
        long y=1L;
        for(long i=2;i<=n;i++){
            //按递推式计算res
            res=((x*c)%mod+(y*b)%mod)%mod;
            //跟新x、y
            x=y;
            y=res;
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：循环总共执行了 $n-1$ 次，所以最终的时间复杂度为 $O(n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。

方法二（矩阵快幂法）

1.解题思路

根据递归关系 $a_i=b*a_{i-1}+c*a_{i-2}(i>=2)$ ，可以得出 $图片说明$ ，已知 $a_1=1,a_0=0$ ，所以 $图片说明$ 。

首先处理第0项和第1项的结果。
然后自定义矩阵乘法和矩阵快幂法。
根据矩阵快幂法计算出基数矩阵的 $n-1$ 次幂，结果矩阵的第一行第一列即为 $a_n$ 的值。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 输出序列的第n项
     * @param n long长整型 序列的项数
     * @param b long长整型 系数
     * @param c long长整型 系数
     * @return long长整型
     */
    //取余常数
    int mod=1000000007;
    public long nthElement (long n, long b, long c) {
        //特殊情况处理
        if(n==0) return 0;
        if(n==1) return 1;
        //基数矩阵
        long[][] base=new long[][]{{b,c},{1,0}};
        //求base的n-1次幂
        long[][] res=fastpow(base,n-1);
        return res[0][0];
    }

    //自定义矩阵乘法
    private long[][] multiply(long[][] x,long[][] y){
        long[][] res=new long[2][2];
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                res[i][j]=(x[i][0]*y[0][j]%mod+x[i][1]*y[1][j]%mod)%mod;
            }
        }
        return res;
    }

    //矩阵快幂法
    private long[][] fastpow(long[][] x,long k){
        long[][] res=new long[][]{{1,0},{0,1}};
        while(k>0){
            //如果是奇数，res乘以x
            if(k%2==1){
                res=multiply(res,x);
            }
            //如果是偶数，x等于x乘以自身，k减半
            x=multiply(x,x);
            k/=2;
        }
        return res;
    }

}

3.复杂度分析

时间复杂度：按矩阵快幂法计算 $base$ 的 $n-1$ 次幂时，总共需要计算 $log_2{n-1}$ 次，所以最终的时间复杂度为 $O(log_2n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。