ps：今天和战友聊到矩阵快速幂，想到前几天学长推荐去刷矩阵专题，挑了其中唯一一道中文题，没想到越过山却被河挡住去路。。。
题目链接：[kuangbin带你飞]专题十九 矩阵 R - M斐波那契数列
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
题意
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取模后的值即可，每组数据输出一行。
思路
一看到题，就拿二维01矩阵变来变去尝试半天，无果，就手推了几部，猛然发现f[i] = a^fib[i- 1]*b^fib[i]。道友们动动手，很容易就能发现。
然后就是刷刷的矩阵快速幂求fib，求出两数，再快速幂，结果得出，俩样例试过没问题，提交，wrong。。。
找来找去，找不出错误在哪，去百度了下，发现别人在对矩阵快速幂的时候都是对MOD-1取余的，顿时纳闷，才发现自己忽略了a^b时迭代时不能直接取余的。
看解释说是由费马小定理可以得出循环节是MOD-1，所以对MOD-1取余。仔细的看了费马小定理，似懂非懂的，至于循环节，压根就没想通，可怜在数论上几近一张白纸的我。(ps：过两天好好研究研究)
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <map>
using namespace std;
#define LL long long
const int MOD = 1000000007;
struct Node
{
LL a, b, c, d;
Node(){};
Node(LL a, LL b, LL c, LL d)
:a(a),b(b),c(c),d(d){}
Node operator*(const Node& t)
{
Node ans;
ans.a = ((this->a*t.a)%(MOD-1)+(this->b*t.c)%(MOD-1))%(MOD-1);
ans.b = ((this->a*t.b)%(MOD-1)+(this->b*t.d)%(MOD-1))%(MOD-1);
ans.c = ((this->c*t.a)%(MOD-1)+(this->d*t.c)%(MOD-1))%(MOD-1);
ans.d = ((this->c*t.b)%(MOD-1)+(this->d*t.d)%(MOD-1))%(MOD-1);
return ans;
}
};
LL qpower(LL n, LL x)
{
LL ans = 1;
LL p = x;
while(n)
{
if(n & 1)
ans = (ans*p)%MOD;
p = (p*p)%MOD;
n >>= 1;
}
return ans;
}
int main()
{
LL a, b, n;
while(cin>>a>>b>>n)
{
Node p = Node(0, 1, 1, 1);
Node ans = Node(1, 0, 0, 1);
if(n == 0)
{
cout<<a<<endl;
continue;
}
--n;
while(n)
{
if(n & 1)
ans = ans*p;
p = p*p;
n >>= 1;
}
LL fiba = ans.b;
LL fibb = ans.d;
LL rel = 0;
rel = (qpower(fiba, a) * qpower(fibb, b))%MOD;
cout<<rel<<endl;
}
}