首页 > 代码库 > 矩阵快速幂 [HDU 4549] M斐波那契数列

矩阵快速幂 [HDU 4549] M斐波那契数列

2024-08-04 14:45:03   213人阅读

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]的值吗？
 

 

Input
输入包含多组测试数据；
每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）
 

 

Output
对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。
 

 

Sample Input
0 1 06 10 2
 

 

Sample Output
060
 

 

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 2ll quickadd(ll a,ll b)           //矩阵快速加，防溢出，其实可以不用这个{    ll ret=0;    while(b)    {        if(b&1)        {            ret+=a;             if(ret>=MOD) ret-=MOD;        }        a<<=1;        if(a>=MOD) a-=MOD;        b>>=1;    }    return ret;}ll quickpow(ll a,ll b)           //矩阵快速幂{    ll ret=1;    while(b)    {        if (b&1) ret=quickadd(a,ret);        a=quickadd(a,a);        b>>=1;    }    return ret;}void mul(ll a[N][N],ll b[N][N])  //矩阵相乘{    ll i,j,k;    ll c[N][N]={0};    for(i=0;i<N;i++)    {        for(j=0;j<N;j++)        {            for(k=0;k<N;k++)            {                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%(MOD-1);            }        }    }    for(i=0;i<N;i++)    {        for(j=0;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==0) printf("%I64d\n",A%MOD);        else if(n==1) printf("%I64d\n",B%MOD);  //特判0,1        else        {            n-=2;            ll a[N][N]={1,1},b[N][N]={0,1,1,1};            while(n)            {                if(n&1)mul(a,b);                mul(b,b);                n>>=1;            }            ll k1=a[0][0];            ll k2=a[0][1];            ll ans=1;            ans=ans*quickpow(A,k1)%MOD;            ans=ans*quickpow(B,k2)%MOD;            printf("%I64d\n",ans);        }    }    return 0;}

 

矩阵快速幂 [HDU 4549] M斐波那契数列


联系
我们