題意：F[0] = a ,F[1] = b,F[n] = F[n-1] * F[n-2] ( n > 1 )
現(xiàn)在給出a, b, n，你能求出F[n]的值
想到點子上就很簡單了,可當(dāng)時做的時候都沒有向找遞推式的方向去思考
1.找F[n]的遞推式

附：斐波那契數(shù)矩陣公式
?Fn+1 ? Fn ? ? ? ?1 ? ?1
? ? ? ? ? ? ? ? ? ? ?=? ? ? ? ? ? ?的n次方
?Fn ? ? Fn-1? ? ? ?1? ? ?0

#include <bits/stdc++.h> #define X 10005 #define inf 0x3f3f3f3f #define PI 3.141592653589793238462643383 using namespace std; typedef long long ll; const int mod=1e9+7; struct node {ll e[2][2]; } f; node Matrix(node a,node b) {node ans;for(int i=0; i<2; ++i){for(int j=0; j<2; ++j){ans.e[i][j]=0;for(int k=0; k<2; ++k)if(a.e[i][k]&&b.e[k][j])//ans.e[i][j]=(ans.e[i][j]+(a.e[i][k]*b.e[k][j])%(mod-1))%(mod-1); 相等ans.e[i][j]=(ans.e[i][j]+(a.e[i][k]*b.e[k][j]))%(mod-1);}}return ans; } node Pow(node a,int n) {node E;E.e[0][0]=E.e[1][1]=1;E.e[0][1]=E.e[1][0]=0;while(n){if(n&1) E=Matrix(E,a);a=Matrix(a,a);n/=2;}return E; } ll Pow_(ll a,ll n) {ll ans=1;while(n){if(n&1)ans=ans*a%mod;a=a*a%mod;n/=2;}return ans%mod; } int main() {ll a,b,n;while(scanf("%lld %lld %lld",&a,&b,&n)!=EOF){f.e[0][0]=f.e[0][1]=f.e[1][0]=1,f.e[1][1]=0;if(n==0){cout<<a<<endl;}else{f=Pow(f,n-1);ll x=f.e[1][0];ll y=f.e[0][0];printf("%lld\n",Pow_(a,x)*Pow_(b,y)%mod);}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的hdu4549 M斐波那契数列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。