首页 > ACM题库 > 九度OJ > 九度-1081-递推数列[解题代码]
2013
12-12

九度-1081-递推数列[解题代码]

题目来源:2009年清华大学计算机研究生机试真题

题目描述:

给定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

cpp 代码如下:
#include <iostream>
#include <stdio.h>
using namespace std;
const int MOD=10000;
class M{
public:
	long long a,b,c,d;
	M(long long _a,long long _b,long long _c,long long _d):a(_a),b(_b),c(_c),d(_d){}
};
M operator * (M & m1, M & m2){
	return M(
		(m1.a * m2.a + m1.b * m2.c)%MOD,
		(m1.a * m2.b + m1.b * m2.d)%MOD,
		(m1.c * m2.a + m1.d * m2.c)%MOD,
		(m1.c * m2.b + m1.d * m2.d)%MOD
	);
}
int a0,a1,p,q,k;
int main() {
	while(scanf("%lld%lld%lld%lld%lld", &a0, &a1, &p, &q, &k) != EOF){
		M ans(1,0,0,1); //单位阵
		M m(p%MOD,q%MOD,1,0);

		//k--;
		  if (k == 0) cout << a0 % 10000 << endl;
		  else if (k == 1) cout << a1 % 10000 << endl;
		  else{
			  k--;
			  while(k){
			  			if(k & 1){
			  				ans = ans * m;
			  			}
			  			m = m * m;
			  			k >>= 1;
			  		}
			  cout << (ans.a *a1 %MOD+ ans.b * a0 % MOD) %MOD << endl;
		  }

	}
	return 0;
}
/**************************************************************
	Problem: 1081
	User: coder
	Language: C++
	Result: Accepted
	Time:20 ms
	Memory:1520 kb
****************************************************************/


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。