【题解】数列求值
数列求值
题意
已知 ,现在给你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 } };