本文主要是介绍【矩阵快速幂】HDU 4549 : M斐波那契数列（矩阵嵌套），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目链接】click here~~
【题目大意】
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[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。
【Source】 :2013金山西山居创意游戏程序挑战赛――初赛（2）
【解题思路】
这个题稍微有点难度，就是要考虑矩阵里面嵌套矩阵，这样的话，我们就要分别计算左右两边的值，然后再用一次快速幂求出最后的答案,
思考如下：
写出F(2)、F(3)、F(4)、F(5)…会发现a和b的指数是fibonacci数，如果求出fib数列，用快速幂就可以快速求出最后答案。问题转化为了如何快速求解fib数列。 因为【F(n-2)，F(n-1)】*【0,1,1,1】 = 【F(n-1),F(n)】，所以可以用矩阵乘法来求。 每次相乘的矩阵为 0 1 1 1 为了防止求F(n)时溢出，要对矩阵元素取模，即 a[i][j] %= 1000000006。模数之所以为1000000006是因为根据费马小定理可得A^euler(M) = 1 （mod M）,其中M为素数。 所以A^N = A^（N % euler(M)）（mod M），而1000000007为数，euler（1000000007）= 1000000006，所以模数是1000000006。 求出F(n-1)和F(n)以后，用二分快速幂求出pow（a，F(n-1)）* pow（b，F(n)）% 1000000007 就是最后的答案。
代码
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
const int MOD1=1e9+7;
const int MOD2=1e9+6;
#define LL long long
struct Matrlc
{LL map[2][2];
};
Matrlc unit = {1,0,0,1};
Matrlc mult(Matrlc a,Matrlc b)
{Matrlc c;for(int i=0; i<2; i++)for(int j=0; j<2; j++){c.map[i][j]=0;for(int k=0; k<2; k++)c.map[i][j]+=(a.map[i][k]*b.map[k][j])%MOD2;c.map[i][j]%=MOD2;}return c;
}
Matrlc pow1(Matrlc a,LL n)
{Matrlc ans=unit;Matrlc res=a;while(n){if(n&1) ans=mult(ans,res);res=mult(res,res);n>>=1;}return ans;
}
LL pow2(LL a,LL b)
{LL res=1;LL ans=a%MOD1;while(b){if(b&1) res=res*ans%MOD1;ans=ans*ans%MOD1;b>>=1;}return res;
}
int main()
{LL A,B,N,i,j;Matrlc tmp;tmp.map[0][0]=0;tmp.map[0][1]=tmp.map[1][0]=tmp.map[1][1]=1;while(cin>>A>>B>>N){Matrlc p=pow1(tmp,N);LL result=pow2(A,p.map[0][0])*pow2(B,p.map[0][1])%MOD1;printf("%lld\n",result);}return 0;
}
这篇关于【矩阵快速幂】HDU 4549 : M斐波那契数列（矩阵嵌套）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
