九度OJ 1081：递推数列 （递归，二分法）

本文主要是介绍九度OJ 1081：递推数列 （递归，二分法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

直接一步一步的递推肯定是要超时的。对这种求第n个数的递推题，有logn的解法。

基本思想是a(n)由a(n/2)得到，逐次循环。

由an=p*a(n-1) + q*a(n-2)

可以得到an=p2*a(n-2) + q2*a(n-4)

其中 p2 = (p*p+2*q)， q2 = -q*q

这种思想是典型二分法，此题重点是学到了一种解题思想。

代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>int main(void)
{int p, q, p2, q2, k;long long a0, a1, a2, a3;while (scanf("%lld%lld%d%d%d", &a0, &a1, &p, &q, &k) != EOF){if (k == 0){printf("%lld\n", a0);continue;}a0 %= 10000;a1 %= 10000;p %= 10000;q %= 10000;while (k>1){a2 = p*a1+q*a0;while (a2<0)a2 += 1000000000;a2 %= 10000;if (k%2 == 1){a3 = p*a2+q*a1;while (a3<0)a3 += 1000000000;a3 %= 10000;a0 = a1;a1 = a3;}elsea1 = a2;p2 = (p*p+2*q)%10000;q2 = -q*q;while (q2<0)q2 += 1000000000;q2 %= 10000;p = p2;q = q2;k /= 2;}printf("%lld\n", a1);}return 0;
}
/**************************************************************Problem: 1081User: liangrx06Language: CResult: AcceptedTime:10 msMemory:912 kb
****************************************************************/

别人的代码，用了另一种递归方式，思想是类似的：

#include<stdio.h>
#define MOD 10000
long long a0,a1,p,q,k;
void matrixpow(long long *data,long long k)
{long long t1,t2,t3,t4;        long long d1,d2,d3,d4;d1 = p;d2 = q;d3 = 1;d4 = 0;if(k == 1 || k == 0)return;        matrixpow(data,k/2);t1 = (data[0]*data[0]+data[1]*data[2])%MOD;t2 = (data[0]*data[1]+data[1]*data[3])%MOD;t3 = (data[0]*data[2]+data[2]*data[3])%MOD;t4 = (data[1]*data[2]+data[3]*data[3])%MOD;data[0] = t1;data[1] = t2;data[2] = t3;data[3] = t4;if(k&1){t1 = (data[0]*d1+data[1]*d3)%MOD;t2 = (data[0]*d2+data[1]*d4)%MOD;t3 = (data[2]*d1+data[3]*d3)%MOD;t4 = (data[2]*d2+data[3]*d4)%MOD;data[0] = t1;data[1] = t2;data[2] = t3;data[3] = t4;}
}
void main()
{        long long data[4];long long res;while(scanf("%lld%lld%lld%lld%lld",&a0,&a1,&p,&q,&k)!=EOF){data[0] = p;data[1] = q;data[2] = 1;data[3] = 0;matrixpow(data,k-2);if(k == 0)res = a0%MOD;else{if(k == 1)res = a1%MOD;else{if(k>2)res = (data[0]*p*a1+a1*q*data[2]+a0*p*data[1]+a0*q*data[3])%MOD;elseres = (a1*p+a0*q)%MOD;}}printf("%lld\n",res);}
}

这篇关于九度OJ 1081：递推数列 （递归，二分法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---