HDU 3117( Fibonacci Numbers 十大经典之二 :矩阵快速幂的应用)

spoiler posted @ 2011年4月26日 15:37 in 十个利用矩阵乘法解决的经典题目 , 2397 阅读

题目大意:求

Fibonacci Numbers如果位数低于8位,则全部输出,否则只输出

前4位与后4位(注意后四位的0别忘记了,不过是什么格式,哪怕

0000都要输出);

题目分析:这里我们上一篇文章以前具体阐述了:

给定矩阵A,请快速计算出A^n(n个A相乘)的结果,输出的每个数都mod p。
由 于矩阵乘法具有结合律,因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我们可以得到这样的结论:当n为偶数时,A^n = A^(n/2) * A^(n/2);当n为奇数时,A^n = A^(n/2) * A^(n/2) * A (其中n/2取整)。这就告诉我们,计算A^n也可以使用二分快速求幂的方法。例如,为了算出A^25的值,我们只需要递归地计算出A^12、A^6、 A^3的值即可。根据这里的一些结果,我们可以在计算过程中不断取模,避免高精度运算。

然后我们以前有一篇文章已经阐述了,如果利用取对数求第N个fibonacci数的前4位有效数字;如果不清楚的话 请看我以前的一篇文章

“HDU 1568(非常经典微妙的 斐波纳契计算)“

代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int sim[50]={0};
double f=(1+sqrt(5.0))/2;
double ff=(1-sqrt(5.0))/2;
struct M{
	int s[5][5];
};
int solve_f4(int n){
	double t=(-0.5)*log(5.0)/log(10.0)+(double(n))*log(f)/log(10.0);
	double k=t-floor(t);
	t=pow(10.0,k);
	while(t<1000)
		t*=10.0;
	return (int)t;
}
struct M multiply(struct M a,struct M b){
	struct M c;
	memset(c.s,0,sizeof(c.s));
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			for(int k=1;k<=2;k++)
				c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%10000)%10000;
	return c;
}
struct M paw(struct M a,int t){
	if(t==1)
		return a;
	else{
		struct M k=paw(a,t/2);
		if(t&1){
			return multiply(multiply(k,k),a);
		}
		else
			return multiply(k,k);
	}
}
int main(){
	int n,k1,k2;
	struct M a,b;
	a.s[1][1]=1;
	a.s[1][2]=0;
	a.s[2][1]=0;
	a.s[2][2]=1;
	b.s[1][1]=b.s[1][2]=b.s[2][1]=1;
	b.s[2][2]=0;
	sim[0]=0;
	sim[1]=1; sim[2]=1; sim[3]=2;
	for(int i=4;i<=49;i++)
		sim[i]=sim[i-2]+sim[i-1];
	while(scanf("%d",&n)!=EOF){
		if(n<=39){
			printf("%d\n",sim[n]);
			continue;
                     //其实我最初是用公式求前39个fibonacci数的
                     //但是发现有误差,所以改用数组直接模拟出来
		}
		else{
			k1=solve_f4(n);
			struct M k=paw(b,n-1);
			k=multiply(k,a);
			k2=k.s[1][1]%10000;
			printf("%d...%04d\n",k1,k2);
		}
	}
	return 0;
}


 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter