数列求值

题意

已知 ,现在给你b和c两个系数的值，请你求出 除以 的余数。

解法1

从第二项开始逐项按照以上式子递推出第n项的值
时间复杂度：
空间复杂度：

代码

class Solution {
public:
    /**
     * 输出序列的第n项
     * @param n long长整型 序列的项数
     * @param b long长整型 系数
     * @param c long长整型 系数
     * @return long长整型
     */
    static const long long MOD = 1e9+7;
    long long nthElement(long long n, long long b, long long c) {
       long long f0=0,f1=1;
       for(long long i=2;i<=n;i++)
       {
         long long f2=(b*f0%MOD+c*f1%MOD)%MOD;
         f0=f1;
         f1=f2;
        }
      return f1;
    }
};

解法2

以上解法时间复杂度太高，无法通过所有测试数据。
注意到
根据矩阵乘法的结合律，我们可以推出

使用矩阵乘法快速幂，我们可以对以上递推进行加速，从而通过这道题。
时间复杂度：
空间复杂度：

代码

class Matrix
{
    public:
   static const long long MOD = 1e9+7;
    int n,m;
    long long val[2][2];
    Matrix operator*(Matrix b)
    {
        Matrix c;
        c.n = n;
        c.m = b.m;
        memset(c.val,0,sizeof(c.val));
        for(int i=0;i<c.n;i++)
        for(int j=0;j<c.m;j++)
        for(int k=0;k<m;k++)
        c.val[i][j]=(c.val[i][j]+val[i][k]*b.val[k][j]%MOD)%MOD;
        return c;
    }
};

class Solution {
public:
    /**
     * 输出序列的第n项
     * @param n long长整型 序列的项数
     * @param b long长整型 系数
     * @param c long长整型 系数
     * @return long长整型
     */
    Matrix qpow(Matrix a,long long n)
{
    if(n==1)return a;
    Matrix tmp = qpow(a,n>>1);
    tmp = tmp*tmp;
    if(n&1)tmp = tmp*a;
    return tmp;
 } 
    long long nthElement(long long n, long long b, long long c) {
        Matrix a;
    a.m=a.n=2;
    a.val[0][0]=0;
    a.val[0][1]=b;
    a.val[1][0]=1;
    a.val[1][1]=c;
    a=qpow(a,n-1);
    return a.val[1][1];// write code here
    }
};