题目1081：递推数列

2019-04-14 17:10发布

站内文章 / 模拟电子
17127 0 1552
题目描述：
给定a0,a1,以及an=p*a(n-1) + q*a(n-2)中的p,q。这里n >= 2。 求第k个数对10000的模。
输入：
输入包括5个整数：a0、a1、p、q、k。
输出：
第k个数a(k)对10000的模。
样例输入：
20 1 1 14 5
样例输出：
8359

方法一：采用递归求解，Runtime Error(k过大时，递归太深)

#include #include long long a0,a1,p,q,k; long long Ditui(long long n) { if(n == 0) return a0 % 10000; else if(n == 1) return a1 % 10000; else return (p * Ditui(n-1) + q * Ditui(n-2)) % 10000; } int main() { while(scanf("%lld %lld %lld %lld %lld",&a0,&a1,&p,&q,&k) != EOF) { printf("%lld ",Ditui(k)); } }

方法二：采用循环求解，Time limit exceed

#include #include int main() { long long a0,a1,p,q,k; while(scanf("%lld %lld %lld %lld %lld",&a0,&a1,&p,&q,&k) != EOF) { long long *tmp = (long long *)malloc(sizeof(long long) * (k+1)); tmp[0] = a0; tmp[1] = a1; for(long long i = 2;i <= k; i++) { tmp[i] = p * tmp[i - 1] + q * tmp[i - 2]; } printf("%lld ",tmp[k]); } }

方法三：采用矩阵相乘

原理：将线性递推公式an=p*a(n-1) + q*a(n-2)转化成矩阵相乘。
#include #include #include struct Matrix { long long int a[2][2]; }; //矩阵乘法 Matrix MatrixPly(Matrix x,Matrix y) { Matrix tmp; memset(tmp.a,0,sizeof(tmp.a)); for(int i = 0;i < 2;i++) for(int j = 0;j < 2;j++) for(int k = 0;k < 2;k++) tmp.a[i][j] = (tmp.a[i][j] + x.a[i][k] * y.a[k][j]) % 10000; return tmp; } //矩阵的快速幂运算 Matrix MatrixPow(Matrix x,long long int n) { Matrix res; memset(res.a,0,sizeof(res.a)); res.a[0][0] = res.a[1][1] = 1;//二维数组 while(n) { if(n & 1) res = MatrixPly(res,x); n>>=1; x = MatrixPly(x,x); } return res; } //矩阵递归求其幂运算 Matrix MatrixPow2(Matrix r , long long int k) { Matrix temp; if(k==1) return r; if(k==2) return MatrixPly(r,r); else { if(k%2==0) { temp = MatrixPow2(r ,k/2); temp = MatrixPly(temp,temp); return temp; } else { temp = MatrixPow2(r ,k/2); temp = MatrixPly(temp ,temp); temp = MatrixPly(temp,r); return temp; } } } int main() { long long int a0,a1,p,q,k; while(scanf("%lld %lld %lld %lld %lld",&a0,&a1,&p,&q,&k) != EOF) { if(k == 0) printf("%lld",a0 % 10000); if(k == 1) printf("%lld",a1 % 10000); else { Matrix init,result; init.a[0][0] = p;init.a[0][1] = q; init.a[1][0] = 1;init.a[1][1] = 0; result = MatrixPow2(init,k-1); printf("%lld ",(result.a[0][0] * a1 + result.a[0][1] * a0) % 10000); } } }
注：本机跑是没问题，OJ上提交会出现Runtime Error,至今不知道什么问题，若知道解决方案的，求指导！

热门文章