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

题目链接

题目

---

 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

---

题意:

emmm,中文题,不解释,

思路:

矩阵快速幂,

分析一下题目给的递推式:
f[0] = a;
f[1] = b;
f[2] = a * b;
f[3] = $a * b^{2}$;
f[4] = $a^ 2 * b^{3}$;
f[5] = $a ^ 3 * b^{5}$;
f[6] = $a ^ 5 * b^{8}$;
有没有发现第n项的 a, 和 b 的幂恰好是斐波那契数列的第 n - 2,和 n - 3 项.于是快速幂加快速幂就可以了.

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long LL;
const int mod = 1e9+6;
LL a,b,n;

struct mat {
    LL a[3][3];
    mat(){memset(a, 0,sizeof(a)); }
    mat operator *(const mat q){
        mat c;
        for(int i = 1; i <= 2; ++i)
            for(int j = 1; j <= 2; ++j)
            if(a[i][j])
        for(int k = 1;  k<= 2; ++k){
            c.a[i][k] += a[i][j] * q.a[j][k];
            if(c.a[i][k] >= mod) c.a[i][k] %= mod;
        }return c;
    }
};

mat qpow(mat x, LL n){
    mat ans;
    ans.a[1][1] = ans.a[2][2] = 1;
    while(n){
        if(n&1) ans =ans * x;
        x = x * x;
        n >>= 1;
    }return ans;
}

LL qpow(LL x,LL n){
    LL ans = 1;
    while(n){
        if (n&1) ans = (ans * x) %( mod + 1);
        x = (x * x) % (mod + 1);
        n >>= 1;
    }return ans;
}

int main(){
    while(scanf("%lld %lld %lld", &a, &b, &n) != EOF){
        a %= (mod + 1);
        b %= (mod + 1);
        if (n == 0) {
            printf("%lld\n",a);
            continue;
        } if(n == 1){
        printf("%lld\n",b);
        continue;
        }mat ans;
        ans.a[2][2] =ans.a[1][2] = ans.a[2][1] = 1;
        ans =qpow(ans, n);//算斐波那契数列
        LL n1 = ans.a[1][1];
        LL n2 = ans.a[2][1];
        a = qpow(a, n1);
        b = qpow(b, n2);
        LL sum = a * b %( mod +1 );
        printf("%lld\n",sum);
    }return 0;
}