hdoj M斐波那契數列 4549&nyoj 又見斐波那契數列 1000 (矩陣快速幂&規律)

M斐波那契數列

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 2416    Accepted Submission(s): 701

Problem Description M斐波那契數列F[n]是一種整數數列，它的定義如下：

F[0] = a

F[1] = b

F[n] = F[n-1] * F[n-2] ( n > 1 )

現在給出a, b, n，你能求出F[n]的值嗎？  

Input 輸入包含多組測試資料；

每組資料占一行，包含3個整數a, b, n（ 0 <= a, b, n <= 10^9 ）  

Output 對每組測試資料請輸出一個整數F[n]，由于F[n]可能很大，你隻需輸出F[n]對1000000007取模後的值即可，每組資料輸出一行。  

Sample Input

0 1 0
6 10 2
        

Sample Output

0
60      

思路：

 先找規律  f(0)=a        (1,0)

                f(1)=b;       (0,1)

                f(2)=ab      (1,1)

                f(3)=abb     (1,2)

                f(4)=abbab   (2,3)

                f(5)=abbababb    (3,5)

                f(6)=abbababbabbab  (5,8)

                .......

由上面的規律可以看出 f[n]=a^m0*b^m1%M.(m0,m1都為斐波那契數列)

是以先求出m0,m1，再求出 a^m0*b^m1%M就行了。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 0x3f3f3f3f
#define ll long long
#define N 2
#define M 1000000007
using namespace std;
ll a,b,n;
struct mat 
{
	ll m[N][N];
};
mat A=
{
	1,1,
	1,0
};
mat I=
{
	1,0,
	0,1
};
mat multi(mat a,mat b)//兩矩陣相乘 
{
	int i,j,k;
	mat c;
	for(i=0;i<N;i++)
	{
		for(j=0;j<N;j++)
		{
			c.m[i][j]=0;
			for(k=0;k<N;k++)
			{
				c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%(M-1))%(M-1);
			}
		}
	}
	return c;
}
mat power(mat A,int k)//矩陣快速幂
{
	mat ans=I,p=A;
	while(k)
	{
		if(k&1)
			ans=multi(ans,p);	
		p=multi(p,p);
		k>>=1;
	}
	return ans;
}
ll ppower(ll k,ll m)//整數快速幂 
{
	ll ans=1;
	while(m)
	{
		if(m&1)
			ans=(ans*k%M);
		k=(k*k%M);
		m>>=1;
	}
	return ans;
}
int main()
{
	while(scanf("%d%d%d",&a,&b,&n)!=EOF)
	{
		if(n==0)
		{
			printf("%lld\n",a);
			continue;
		}
		mat ans=power(A,n-1);
		ll ansa=ppower(a,ans.m[0][1]);
		ll ansb=ppower(b,ans.m[0][0]);
		ll s=(ansa*ansb)%M;
		printf("%lld\n",s);
	}
	return 0;
}