本文主要是介绍hdu 4549 M斐波那契数列（矩阵乘法+降幂公式），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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
Sample Output
0 60
Source
2013金山西山居创意游戏程序挑战赛——初赛（2）
Recommend
liuyiding
让求F[n]，公式里面是乘法，不好构造矩阵，但是发现乘法的幂次是相加的：
f0 = a;
f1 = b;
f2 = f0*f1;
f3 = f0 * (f1^2);
f4 = (f0^2) * (f1^3);
f5 = (f0^3) * (f1^5);
可以发现第i项的f0的幂次等于前两项f0幂次的和，f1的幂次同样也是。（其实就是斐波那契数列）
但是还有一个问题，a^(n%mod) != (a^n)%mod，这样我们就得用到降幂公式：
(a^n)%mod = (a^(n%(mod-1)))%mod; (mod是质数)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;const int mod = 1000000006;struct Matrix
{long long m[2][2];int n;Matrix(int x){n = x;for(int i=0;i<n;i++)for(int j=0;j<n;j++)m[i][j] = 0;}Matrix(int _n,int a[2][2]){n = _n;for(int i=0;i<n;i++)for(int j=0;j<n;j++){m[i][j] = a[i][j];}}
};
Matrix operator *(Matrix a,Matrix b)
{int n = a.n;Matrix ans = Matrix(n);for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++){ans.m[i][j] += (a.m[i][k]%mod)*(b.m[k][j]%mod)%mod;ans.m[i][j] %= mod;}return ans;
}
Matrix operator ^(Matrix a,int k)
{int n = a.n;Matrix c(n);int i,j;for(i=0;i<n;i++)for(j=0;j<n;j++)c.m[i][j] = (i==j);for(;k;k>>=1){if(k&1)c=c*a;a = a*a;}return c;
}LL quickpow(LL x,int k,int m)
{LL ans = 1;while(k){if(k&1)ans = ans*x%m;x = x*x%m;k /= 2;}return ans;
}
int main(void)
{int x,y,n,i,j;while(scanf("%d%d%d",&x,&y,&n)==3){int a[2][2] = { 0,1,1,1};Matrix A(2,a);int b[2][2] = { 1,0,0,1};Matrix B(2,b);A = A^n;A = A*B;int k1 = A.m[0][0];int k2 = A.m[0][1];LL ans = (quickpow(x,k1,mod+1)*quickpow(y,k2,mod+1))%(mod+1);cout << ans << endl;}return 0;
}
这篇关于hdu 4549 M斐波那契数列（矩阵乘法+降幂公式）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
