首页 > ACM题库 > HDU-杭电 > HDU 4549-M斐波那契数列-快速幂-[解题报告]HOJ
2015
07-25

HDU 4549-M斐波那契数列-快速幂-[解题报告]HOJ

M斐波那契数列

问题描述 :

M斐波那契数列F[n]是一种整数数列,它的定义如下:

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

现在给出a, b, n,你能求出F[n]的值吗?

输入:

输入包含多组测试数据;
每组数据占一行,包含3个整数a, b, n( 0 <= a, b, n <= 10^9 )

输出:

输入包含多组测试数据;
每组数据占一行,包含3个整数a, b, n( 0 <= a, b, n <= 10^9 )

样例输入:

0 1 0
6 10 2

样例输出:

0
60

这是一道数学题,刚开始有点吓人。。表面上看没啥思路,于是就是试着写了几个,发现f(n)=a^fib(n-1)*b^fib(n),n>=2,嘿嘿,这下有了

然而今晚状态真是差的一塌糊涂,各种错误+各种NC思路。。。哎,不多说,拙计。。。。

求a^fib(n)%mod,mod=10^9+7,由于mod是一个大质数,根据费马小定理,a^(mod-1)=1(mod m),所以a^x有一个循环节,这个循环节为10^9+6

然后就求fib(n)%(mod-1),用矩阵快速幂即可。接下来求a^x用折半快速幂即可。。。其中,由于a,b,n可以去到0,1,在这之前务必考虑一些特殊情况。。。附代码:

#include <iostream>
#include <cstdio>
#include <vector>
 
#define N 32767
#define cl(a) memset(a,0,sizeof(a))
#define mod 1000000007
#define pb push_back
#define ll __int64
#define ss(a) scanf("%d",&a)

using namespace std;

ll f[3][3],f1[3][3],z[3];

ll js(ll n,int k)
{    
    ll res=1,t=n;
    while (k>0)
    {
        if (k&1) res=(res*t)%mod;
        t=(t*t)%mod;
        k>>=1;
    }
    return res;
}

void init()
{
    cl(z);cl(f);
    z[1]=1;z[2]=0;
    f[1][1]=1;f[1][2]=1;
    f[2][1]=1;f[2][2]=0;   
}

void rmul()
{
    int i,j,k;
    for (i=1;i<=2;i++)
        for (j=1;j<=2;j++)
        {
            f1[i][j]=0;
            for (k=1;k<=2;k++) f1[i][j]=(f1[i][j]+f[i][k]*f[k][j])%(mod-1);
        }
    for (i=1;i<=2;i++)
        for (j=1;j<=2;j++) f[i][j]=f1[i][j];
}

void zmul()
{
    ll z1,z2;
    z1=(f[1][1]*z[1]+f[1][2]*z[2])%(mod-1);
    z2=(f[2][1]*z[1]+f[2][2]*z[2])%(mod-1);
    z[1]=z1;
    z[2]=z2;
}

ll fib(int n)
{
    int i;
    init();
    n--;
    if (n&1) zmul();
    n>>=1;
    for (i=1;i<N;i++) 
    {
        rmul();
        if (n&1) zmul();
        n>>=1;
        if (!n) break;
    }
    return z[1]; 
}

int main()
{
    int n,a1,b1;
    while (ss(a1)!=EOF)
    {
        ss(b1);ss(n);
        if (n<2)
        {
            if (!n) cout<<a1%mod<<endl;
            else cout<<b1%mod<<endl;
            continue;
        }
        if (!a1||!b1)
        {
            cout<<0<<endl;
            continue;
        }
        int m1,m2;
        ll res=1;
        if (a1>1) res=res*js(a1,fib(n-1))%mod;
        if (b1>1)res=res*js(b1,fib(n))%mod;
        printf("%d\n",res);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/liverpippta/article/details/8962922