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 ）

Output

對每組測試數據請輸出一個整數F[n]，由于F[n]可能很大，你只需輸出F[n]對1000000007取模后的值即可，每組數據輸出一行。

Sample Input

0 1 0
6 10 2

Sample Output

0
60

思路：

根據 F[0]=a，F[1]=b 與?F[n] = F[n-1] * F[n-2] 進行遞推

有：

其中，f[i] 為斐波那契數列數列，即：f[i]=f[i-1]+f[i-2]

因此，可先根據斐波那契數列構造矩陣，求出 f[n-1] 與 f[n]，然后直接求 F[n]

構造矩陣，有：

化簡，得：

那么：

由于 n 最大可達到 1E9，f[n] 與 f[n-1] 會很大，要求的 ?一定會爆

因此要使用費馬小定理降冪

根據費馬小定理：

那么：

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-9 #define INF 0x3f3f3f3f #define LL long long const int MOD=1000000007; const int N=10+5; const int dx[]= {-1,1,0,0}; const int dy[]= {0,0,-1,1}; using namespace std; struct Matrix{LL s[N][N]; }; Matrix e;//單位矩陣E Matrix x;//構造矩陣void init(){for(int i=1;i<=2;i++)//主對角線為1e.s[i][i]=1; } Matrix mul(Matrix A,Matrix B,LL n){//矩陣乘法，n代表A、B兩個矩陣是n階方陣Matrix temp;//臨時矩陣，存放A*B結果for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)temp.s[i][j]=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)temp.s[i][j]=(temp.s[i][j]+A.s[i][k]*B.s[k][j])%(MOD-1);//費馬小定理降冪后模為1E9-1return temp; } Matrix quickPower(Matrix a,LL b,LL n){//矩陣快速冪，求矩陣n階矩陣的b次冪Matrix ans=e;while(b){if(b&1)ans=mul(ans,a,n);//ans=e*aa=mul(a,a,n);//a=a*ab>>=1;}return ans; } LL quickPow(LL a,LL b){//快速冪LL res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res; } int main(){init();LL a,b,n;while(scanf("%lld%lld%lld",&a,&b,&n)!=EOF){LL fa;//a的冪LL fb;//b的冪if(n==0){fa=1;fb=0;}else if(n==1){fa=0;fb=1;}else if(n==2){fa=1;fb=1;}else{x.s[1][1]=1;x.s[1][2]=1;x.s[2][1]=1;x.s[2][2]=0;Matrix res=quickPower(x,n-2,2);//注意MOD降冪fa=((res.s[2][1]+res.s[2][2])%(MOD-1)+(MOD-1))%(MOD-1);//fn-1fb=((res.s[1][1]+res.s[1][2])%(MOD-1)+(MOD-1))%(MOD-1);//fn}LL temp1=quickPow(a,fa);//a^f(n-1)LL temp2=quickPow(b,fb);//b^f(n)LL result=(temp1*temp2)%MOD;printf("%lld\n",result);}return 0; }

?

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的M斐波那契数列（HDU-4549）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。