MF( i ) = a ^ fib( i-1 ) * b ^ fib ( i ) ( i>=3)
mod1000000007是质数 , 根据费马小定理 a^phi( p ) = 1 ( mod p ) 这里 p 为质数 且 a 比 p小 所以a^( p – 1 ) = 1 ( mod p )
所以对很大的指数可以化简 a ^ k % p == a ^ ( k %(p-1) ) % p
用矩阵快速幂求fib数后代入即可
M斐波那契数列Time Limit: 3000/1000 MS (Java/Others)Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1672Accepted Submission(s): 482
Problem Description
M斐波那契数列F[n]是一种整数数列，它的定义如下：F[0] = aF[1] = bF[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 06 10 2
Sample Output
060
Source
2013金山西山居创意游戏程序挑战赛——初赛（2）
/* ***********************************************Author:CKbossCreated Time :2015年03月12日 星期四 22时44分35秒File Name:HDOJ4549.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long int LL;const LL mod=1000000007LL;const LL md=1000000006LL;/// getfibLL a,b,n;struct Matrix{Matrix(LL a=0,LL b=0,LL c=0,LL d=0){m[0][0]=a; m[0][1]=b;m[1][0]=c; m[1][1]=d;}LL m[2][2];};Matrix MUI(Matrix& a,Matrix& b){Matrix ret;ret.m[0][0]=((a.m[0][0]*b.m[0][0])%md+(a.m[0][1]*b.m[1][0])%md)%md;ret.m[0][1]=((a.m[0][0]*b.m[0][1])%md+(a.m[0][1]*b.m[1][1])%md)%md;ret.m[1][0]=((a.m[1][0]*b.m[0][0])%md+(a.m[1][1]*b.m[1][0])%md)%md;ret.m[1][1]=((a.m[1][0]*b.m[0][1])%md+(a.m[1][1]*b.m[1][1])%md)%md;return ret;}Matrix QUICKPOW(LL m){Matrix E(1,0,0,1);Matrix A(1,1,1,0);while(m){if(m&1LL) E=MUI(E,A);A=MUI(A,A);m/=2LL;}return E;}void showMat(Matrix M){cout<<endl;for(int i=0;i<2;i++){for(int j=0;j<2;j++)cout<<M.m[i][j]<<",";cout<<endl;}cout<<endl;}/// get p_th fib numberLL getfib(LL p) {p–;Matrix M1=QUICKPOW(p);return M1.m[0][0];}LL QUICKPOW2(LL a,LL x){LL e=1LL;while(x){if(x&1LL) e=(e*a)%mod;a=(a*a)%mod;x/=2LL;}return e;}LL solve(){if(n==0) return a;else if(n==1) return b;else if(n==2) return (a*b)%mod;///a的fib系数 -> fib(n-1)LL xa = getfib(n-1);LL partA = QUICKPOW2(a,xa);///b的fib系数 -> fib(i)LL xb = getfib(n);LL partB = QUICKPOW2(b,xb);return (partA*partB)%mod;}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);while(cin>>a>>b>>n)cout<<solve()<<endl;return 0;}
走走停停，不要害怕错过什么，
