M斐波那契数列
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1609 Accepted Submission(s): 460
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]的值吗？
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 ）
每组数据占一行，包含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
6 10 2
Sample Output
0
60
60
Source
2013金山西山居创意游戏程序挑战赛——初赛（2）
详解：
F(n)=F(n-1)*F(n-2)
F(1)=a;
F(2)=b;
F(3)=a^1*b^1
F(4)=a^1*b^2
F(5)=a^2*b^3
F(6)=a^3*b^5
F(n)=a^f(n'-1)*b^f(n'), f(n')为斐波拉契数列
这样就可以先算出F(n)对应f(n')、f(n'-1),再二分快速幂，F(n)=a^f(n'-1)%MOD*b^f(n')%MOD
另外由于n比较大且MOD为质数，则根据费马小定理得：F(n)=a^(f(n'-1)%(MOD-1)%MOD) * b^(f(n')%(MOD-1))%MOD
注意这里n'和n不一样，当n为3时，f(n')=1,不妨让n'=n-2...
#include <iostream>
#include <cstdio>
using namespace std;
#define MOD 1000000007
#define ll __int64
#define N 2 ll quickadd(ll a,ll b) //矩阵快速加，防溢出，其实可以不用这个
{
ll ret=;
while(b)
{
if(b&)
{
ret+=a;
if(ret>=MOD) ret-=MOD;
}
a<<=;
if(a>=MOD) a-=MOD;
b>>=;
}
return ret;
}
ll quickpow(ll a,ll b) //矩阵快速幂
{
ll ret=;
while(b)
{
if (b&) ret=quickadd(a,ret);
a=quickadd(a,a);
b>>=;
}
return ret;
}
void mul(ll a[N][N],ll b[N][N]) //矩阵相乘
{
ll i,j,k;
ll c[N][N]={};
for(i=;i<N;i++)
{
for(j=;j<N;j++)
{
for(k=;k<N;k++)
{
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%(MOD-);
}
}
}
for(i=;i<N;i++)
{
for(j=;j<N;j++)
{
a[i][j]=c[i][j];
}
}
}
int main()
{
ll A,B,n;
while(scanf("%I64d%I64d%I64d",&A,&B,&n)!=EOF)
{
if(n==) printf("%I64d\n",A%MOD);
else if(n==) printf("%I64d\n",B%MOD); //特判0,1
else
{
n-=;
ll a[N][N]={,},b[N][N]={,,,};
while(n)
{
if(n&)mul(a,b);
mul(b,b);
n>>=;
}
ll k1=a[][];
ll k2=a[][];
ll ans=;
ans=ans*quickpow(A,k1)%MOD;
ans=ans*quickpow(B,k2)%MOD;
printf("%I64d\n",ans);
}
}
return ;
}