M斐波那契数列
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
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]的值吗？
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
6 10 2
Sample Output
0
60
60
Source
思路：原始的斐波那契是F(n)=x*f(1)+y*f(2);
然后同样的本题的F(n)=f(1)^x*f(2)^y;
根据费马小定理，或者欧拉定理，对于指数进行x(y)%(mod-1);
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
#define bug(x) cout<<"bug"<<x<<endl;
const int N=2e5+,M=1e6+,inf=1e9+;
const ll INF=1e18+,mod=1e9+;
ll MOD;
struct Matrix
{
ll a[][];
Matrix()
{
memset(a,,sizeof(a));
}
void init()
{
for(int i=;i<;i++)
for(int j=;j<;j++)
a[i][j]=(i==j);
}
Matrix operator + (const Matrix &B)const
{
Matrix C;
for(int i=;i<;i++)
for(int j=;j<;j++)
C.a[i][j]=(a[i][j]+B.a[i][j])%MOD;
return C;
}
Matrix operator * (const Matrix &B)const
{
Matrix C;
for(int i=;i<;i++)
for(int k=;k<;k++)
for(int j=;j<;j++)
C.a[i][j]=(C.a[i][j]+1LL*a[i][k]*B.a[k][j])%MOD;
return C;
}
Matrix operator ^ (const ll &t)const
{
Matrix A=(*this),res;
res.init();
ll p=t;
while(p)
{
if(p&)res=res*A;
A=A*A;
p>>=;
}
return res;
}
};
ll quickmod(ll a,ll b,ll c)
{
ll ans=;
while(b)
{
if(b&)ans=(ans*a)%c;
b>>=;
a=(a*a)%c;
}
return ans;
}
int main()
{
ll a,b,n;
Matrix base,ans;
base.a[][]=;base.a[][]=;
base.a[][]=;base.a[][]=;
MOD=1e9+;
while(~scanf("%lld%lld%lld",&a,&b,&n))
{
if(n==)
printf("%lld\n",a);
else if(n==)
printf("%lld\n",b);
else
{
ans=base^(n-);
ll x=quickmod(b,ans.a[][],1e9+);
ll y=quickmod(a,ans.a[][],1e9+);
printf("%lld\n",(x*y)%mod);
}
}
return ;
}