hdu4549 矩阵快速幂 + 欧拉降幂

R - M斐波那契数列

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Submit Status Practice HDU 4549

Appoint description:
System Crawler (2016-04-24)

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

列出数列的前几项可以观察得到，每一项的a，b的值满足f[i] = f[i-1] + f[i-2]，所以能够用矩阵构造。但是我们的答案最后要取mod，矩阵里的值可能也会超过long long，

所以也需要降幂，此时可以用欧拉降幂，如果有公式a^x （mod m），并且gcd(x,m)==1，即x和m互质，那么a^x = a^(x % Eular(m));由于m是质数，所以Eular(m) = m - 1;

最后再快速幂、相乘（要取模）即可;

#include<map>

#include<set>

#include<string>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<cstdio>

#include<time.h>

#include<cstring>

#include<iostream>

#include<algorithm>

#define INF 1000000001

#define ll long long

#define MOD 1000000007

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

const int MAXN = ;

struct Mat

{

    ll a[][];

};

ll fa,fb,n;

Mat operator *(Mat a,Mat b)

{

    Mat c;

    memset(c.a,,sizeof(c.a));

    for(int i = ; i < ; i++){

        for(int j = ; j < ; j++){

            for(int k = ; k < ;k++){

                c.a[i][j] += (a.a[i][k] * b.a[k][j])%(MOD-);

            }

        }

    }

    return c;

}

Mat power(Mat b,ll n)

{

    Mat c;

    c.a[][] = c.a[][] = ;

    c.a[][] = c.a[][] = ;

    while(n){

        if(n & ){

            c = c * b;

        }

        b = b * b;

        n >>= ;

    }

    return c;

}

ll mod_pow(ll x,ll n)

{

    ll res = ;

    while(n){

        if(n & ) res = res * x % MOD;

        x = x * x % MOD;

        n >>= ;

    }

    return res;

}

ll mod_mul(ll a,ll b)

{

    ll res = ;

    while(b){

        if(b & ){

            res = (res + a) % MOD;

        }

        b >>= ;

        a = (a + a) % MOD;

    }

    return res;

}

int main()

{

    while(~scanf("%lld%lld%lld",&fa,&fb,&n)){

        if(fa ==  || fb == ){

            cout<<<<endl;

            continue;

        }

        if(n == ){

            cout<<fa%MOD<<endl;

            continue;

        }

        else if(n == ){

            cout<<fb%MOD<<endl;

            continue;

        }

        Mat a;

        a.a[][] = ;

        a.a[][] = a.a[][] = a.a[][] = ;

        a = power(a,n-);

        ll num1 = (a.a[][] + a.a[][])%(MOD-);

        ll num2 = (a.a[][] + a.a[][])%(MOD-);

        ll ans1 = mod_pow(fa,num1);

        ll ans2 = mod_pow(fb,num2);

        ll ans = mod_mul(ans1,ans2);

        printf("%lld\n",ans);

    }

    return ;

}