? 一句話題意：求斐波那契數列第n項，如果位數大于8，則只顯示最前4位和最后4位。

? 題解：對于最后4位，套斐波那契數列的矩陣快速冪模板，MOD為10000即可。

? 而對于最后4位： 已知斐波那契數列通項公式f(n)=(1/√5)?*?[((1+√5)/2)^n-((1-√5)/2)^n]；

? 取對數log10(f(n))=log10(1/√5)+log10( ((1+√5)/2)^n*( 1-[ ((1-√5)/2)/((1+√5)/2) ]^n?) ；

? 即：log10(f(n))=-0.5*log10(5) + n*log10((1+√5)/2)+log10(1-((1-√5)/(1+√5))^n)；

? 當n較大時，((1-√5)/(1+√5))^n趨近于0，則log10(1-((1-√5)/(1+√5))^n)這一項趨近于0，所以可以省略掉。 故在求出-0.5*log10(5) + n*log10((1+√5)/2)后，假設值為X.abcdef，再求10^X.abcdef即為第n項數列的粗略值，將其乘上1000，所取整數部分就是這一項的前4位了。

?

1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #include <set> 7 #include <utility> 8 #include <vector> 9 #include <map> 10 #include <queue> 11 #include <stack> 12 const int inf=0x3f3f3f3f; 13 const double PI=acos(-1.0); 14 const double EPS=1e-8; 15 using namespace std; 16 typedef long long ll; 17 typedef pair<int,int> P; 18 19 const ll mod=10000; 20 int n; 21 int f[40]; 22 void init() 23 { 24 f[0]=0,f[1]=f[2]=1; 25 for(int i=3; i<40; i++) f[i]=f[i-1]+f[i-2]; 26 } 27 typedef struct Marix 28 { 29 ll m[2][2]; 30 }Marix; 31 Marix p={1,1,1,0}; 32 Marix mul(Marix a,Marix b) 33 { 34 Marix c; 35 memset(c.m,0,sizeof(c.m)); 36 // 37 for(int k=0;k<2;k++) 38 for(int i=0;i<2;i++) 39 for(int j=0;j<2;j++) 40 c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod; 41 return c; 42 } 43 Marix pow_mod(Marix a,ll n) 44 { 45 Marix c; 46 for(int i=0;i<2;i++) for(int j=0;j<2;j++) c.m[i][j]=(i==j);//將c初始化為單位矩陣 47 // 48 for(;n;n>>=1) 49 { 50 if(n&1) c=mul(c,a); 51 a=mul(a,a); 52 } 53 return c; 54 } 55 void debug() 56 { 57 } 58 int main() 59 { 60 //freopen("input.txt","r",stdin); 61 //debug(); 62 init(); 63 while(scanf("%d",&n)!=EOF) 64 { 65 if(n<40) 66 { 67 cout<<f[n]<<endl; 68 continue; 69 } 70 // 71 double tans=-0.5*log10(5.0)+1.0*n*log10((1.0+sqrt(5.0))/2.0); 72 ll ans=(ll)(pow(10.0,(double)(tans-(ll)tans))*1000.0); 73 cout<<ans<<"..."; 74 // 75 Marix c=pow_mod(p,n-2); 76 ans=(c.m[0][0]+c.m[1][0])%mod; 77 printf("%04d\n",(int)ans); //注意會有前導0的情況 78 } 79 return 0; 80 }

?

轉載于:https://www.cnblogs.com/geek1116/p/6613329.html

總結

以上是生活随笔為你收集整理的hdu 3117 Fibonacci Numbers的全部內容，希望文章能夠幫你解決所遇到的問題。

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