题意

给定一个形如 的式子，求第n项。

方法一(暴力求解):

暴力递推得到第n项

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) {
        long long last1 = 0,last2 = 1,now;
        const long long mod = 1e9 + 7;
        for (long long i = 0;i < n;++ i) {
            now = (last1 * b) % mod + (last2 * c) % mod;
            now %= mod;
            last2 = last1;
            last1 = now;
        }
        return now;
    }
};

时间复杂度因为是一个一个推过去，所以为
空间复杂度与n无关，为

方法二(正解)

首先我们有快速幂，利用二分，在 的时间内完成求幂。原理是乘法结合律。
而矩阵也同样满足乘法结合律，所以也有类似的方法，称为矩阵快速幂。

看到这种形如 式子，我们都可以利用矩阵乘法，构造出一个矩阵。因为对于矩阵，我们有矩阵快速幂，可以在 的时间内快速得出答案。
我们可以构造矩阵 ,通过公式 进行递推
每次递推一项，只需要乘上一个即可。
对于第n项，只需要计算 的n-1次方即可。

const long long mod = 1e9+7;
class mat{    //矩阵类 
public:
    long long a[2][2];
    mat() {
        memset(a,0,sizeof a);
    }
};
mat mul(const mat& a,const mat& b) {    //2*2矩阵相乘 
    mat res;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int u = 0; u < 2; u++) { 
                res.a[i][j] += (a.a[i][u]*b.a[u][j])%mod;
                res.a[i][j] %= mod;
            }
        }
    }
    return res;
}
mat pow(mat x,long long k) {    //矩阵快速幂 
    if (k == 1) {
        return x;
    }
    long long l = k >> 1;
    mat half = pow(x,l);
    half = mul(half,half);
    if (k & 1) {
        half = mul(x,half);
    }
    return half;
}
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) {
        mat x;    //构造矩阵 
        x.a[0][0] = b;x.a[0][1] = 1;
        x.a[1][0] = c;x.a[1][1] = 0;
        x = pow(x,n-1);
        return x.a[0][0];
    }
};

很显然，使用矩阵快速幂后，时间复杂度为 空间复杂度也为 (因为这里采用了递归的方式，深度为 ，所以空间复杂度也是与其成正比。如果采用迭代的方式，可以降至 )