九度OJ 1081： 递推数列

2019-04-14 08:54发布

站内文章 / 模拟电子
13496 0 1596
data/attach/1904/n7mky18jbd9geozamfjfcxtjn6s6sof7.jpg
题目描述：
给定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
来源：
2009年清华大学计算机研究生机试真题

题目分析1：


一个很显然的想法是递推计算这k+1个数对10000的模，实现如下：

源代码1（TLE）


#include #include #define MOD 10000 int main() { int a0, a1, p, q, k; while(scanf("%d%d%d%d%d", &a0, &a1, &p, &q, &k) != EOF) { int *pa = (int *)malloc(sizeof(int)*(k+1)); pa[0] = a0; pa[1] = a1; int i; for(i = 2; i <= k; i++) //时间复杂度为O(k) pa[i] = (p * pa[i-1] + q * pa[i-2])%MOD; printf("%d ", pa[k]); free(pa); } //system("pause"); return 0; } /************************************************************** Problem: 1081 User: superlc320 Language: C++ Result: Time Limit Exceed ****************************************************************/

题目分析2：


很不幸，超时了。以上算法的时间复杂度为O(k), 当k很大时，会TLE。 再次分析题目，会发现递推公式

进而推出

问题转化为求

这里要用到 矩阵二分乘法。 矩阵二分乘法是一种有效的快速计算矩阵幂的算法。 矩阵二分乘法通常可以将线性递推问题O(n)时间缩短到O（log(n)）。 关于矩阵二分乘法更详细的内容可以问度娘。

源代码2


#include #include #define MOD 10000 //结果取MOD，避免高精度运算 /*将矩阵p与矩阵q相乘，结果存入p矩阵*/ void Matrix_mul(int p[2][2], int q[2][2]) { int i, j, k; int t[2][2]={0}; for(i = 0; i <= 1; i++) for(j = 0; j <= 1; j++) for(k = 0; k <= 1; k++) t[i][j] += p[i][k] * q[k][j]; for(i = 0; i <= 1; i++) for(j = 0; j <= 1; j++) p[i][j] = t[i][j] % MOD; } /*计算p矩阵的n次方，结果存入p矩阵*/ void Matrix_cal(int p[2][2], int n) { int i, j; int t[2][2]; for(i = 0; i <= 1; i++) for(j = 0; j <= 1; j++) t[i][j] = p[i][j]; if(n == 1) return; else if(n & 1) { Matrix_cal(p, n-1); Matrix_mul(p, t); } else { Matrix_cal(p, n/2); Matrix_mul(p, p); } } int main() { int a0, a1, p, q, k; while(scanf("%d%d%d%d%d", &a0, &a1, &p, &q, &k) != EOF) { if(k == 0) printf("%d ", a0); else if(k == 1) printf("%d ", a1); else { int matrix[2][2] = { {p%MOD, q%MOD}, {1, 0} }; Matrix_cal(matrix, k-1); printf("%d ", (a1 * matrix[0][0] + a0 * matrix[0][1]) % MOD); } } //system("pause"); return 0; } /************************************************************** Problem: 1081 User: superlc320 Language: C++ Result: Accepted Time:10 ms Memory:1020 kb ****************************************************************/

热门文章