题意

一个数列 满足递推关系 ，， 。给定 ，求 的值。

解法1：直接递推（TLE）

直接按递推式依次求出 。

代码

const int mod=1000000007;

class Solution {
public:
    /**
     * 输出序列的第n项
     * @param n long长整型 序列的项数
     * @param b long长整型 系数
     * @param c long长整型 系数
     * @return long长整型
     */
    long long nthElement(long long n, long long b, long long c) {
        // write code here
        long long a0=0, a1=1, a2;
        for(long long i=2; i<=n; ++i){
            a2=(a0*c+a1*b)%mod; // 递推
            a0=a1, a1=a2;
        }
        return a2;
    }
};

复杂度分析

空间复杂度：2 阶递推，复杂度
时间复杂度：从 到 都要算一遍，复杂度

解法2：矩阵快速幂

注意到
因此可以利用矩阵快速幂求出，其右上角的元素即为答案。

代码

const int mod=1000000007;
class matrix{
    public:
    int a[2][2];
    matrix(int _a=1, int _b=0, int _c=0, int _d=1){ // 矩阵初始化
        a[0][0]=_a;
        a[0][1]=_b;
        a[1][0]=_c;
        a[1][1]=_d;
    }
    matrix operator * (const matrix &m) const{ // 矩阵乘法
        matrix ret;
        for(int i=0; i<2; ++i){
            for(int j=0; j<2; ++j){
                ret.a[i][j]=0;
                for(int k=0; k<2; ++k){
                    ret.a[i][j]=(ret.a[i][j]+1ll*a[i][k]*m.a[k][j])%mod;
                }
            }
        }
        return ret;
    }
    matrix operator ^ (long long k) const { // 矩阵快速幂
        matrix ret;
        matrix m=(*this);
        while(k){
            if(k&1) ret=ret*m;
            m=m*m;
            k>>=1;
        }
        return ret;
    }
};

class Solution {
public:
    /**
     * 输出序列的第n项
     * @param n long长整型 序列的项数
     * @param b long长整型 系数
     * @param c long长整型 系数
     * @return long长整型
     */
    long long nthElement(long long n, long long b, long long c) {
        // write code here
        matrix m=matrix(0,1,c,b)^n;
        return m.a[0][1];
    }
};

复杂度分析

空间复杂度：需要存储 2 阶递推矩阵，复杂度
时间复杂度：需要进行 次矩阵乘法运算，复杂度