题解 | #数列求值#

数列求值

http://www.nowcoder.com/practice/3dfb8d459a2e439bb041c2503d14e5c2

题意：

定义数列 $a_0=0$ ， $a_1=1$ ， $a_n=b*a_{n-1}+c*a_{n-2}$ ，求 $a_nmod(10^9+7)$ 的值

解法一（暴力递推，不可AC）

一个显然的做法就是直接循环一遍递推过去求 $a_n$ 的值

代码：

class Solution {
public:
    const int mod=1e9+7;
    long long nthElement(long long n, long long b, long long c) {
        vector<int> a(n+1);//a数列长度为n+1
        a[0]=0,a[1]=1;//边界
        for(long long i=2;i<=n;i++){
            a[i]=(1ll*b*a[i-1]%mod+1ll*c*a[i-2]%mod)%mod;
            //递推
        }
        return a[n];
    }
};

时间复杂度： $O(n)$ ，我们一共循环了 $n-1$ 次，循环体内的时间复杂度为 $O(1)$ ，故总的时间复杂度为 $O(n)$

空间复杂度： $O(n)$ ，数组的长度为 $n+1$ ，故总的空间复杂度为 $O(n)$

解法二（矩阵快速幂）

由 $a_n=b*a_{n-1}+c*a_{n-2}$ 我们可以构造矩阵乘法 $\left[ \begin{matrix} a_n\\ a_{n-1} \\ \end{matrix} \right]=\left[ \begin{matrix} b & c \\ 1 & 0 \\ \end{matrix} \right]*\left[ \begin{matrix} a_{n-1} \\ a_{n-2} \\ \end{matrix} \right]$

从而得到 $\left[ \begin{matrix} a_n \\ a_{n-1} \\ \end{matrix} \right]=\left[ \begin{matrix} b & c \\ 1 & 0 \\ \end{matrix} \right]^{n-1}*\left[ \begin{matrix} a_1 \\ a_0 \\ \end{matrix} \right]$

因此我们只需要用矩阵快速幂算法求出 $\left[ \begin{matrix} b & c \\ 1 & 0 \\ \end{matrix} \right]^{n-1}$ 即可求出答案

代码：

class Solution {
public:
    static const int mod=1e9+7;
    struct mat{
        int A[2][2];//存放矩阵的值
        inline mat(){
            memset(A,0,sizeof A);//初始化全为0
        }
        inline mat operator * (const mat& other)const{
            mat ret;
            for(int i=0;i<2;i++){
                for(int j=0;j<2;j++){
                    for(int k=0;k<2;k++){
                        //矩阵乘法
                        ret.A[i][j]+=1ll*A[i][k]*other.A[k][j]%mod;
                        ret.A[i][j]%=mod;
                    }
                }
            }
            return ret;
        }
    };
    mat ksm(mat a,long long b){
        mat ret;
        for(int i=0;i<2;i++){
            ret.A[i][i]=1;//单位矩阵
        }
        while(b){
            //矩阵快速幂
            if(b&1){
                ret=ret*a;
            }
            a=a*a;
            b>>=1;
        }
        return ret;
    }
    long long nthElement(long long n, long long b, long long c) {
        mat t;
        t.A[0][0]=b,t.A[0][1]=c;
        t.A[1][0]=1,t.A[1][1]=0;
        t=ksm(t,n-1);
        return t.A[0][0];//模拟矩阵乘法（t.A[0][0]*a[1]+t.A{0][1]*a[0]）
    }
};