hdu 3117 Fibonacci Numbers

  一句话题意：求斐波那契数列第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 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include <set>
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
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<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<"...";
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 }
技巧数论矩阵·快速幂

相关

1.css布局技巧

7个有用的JavaScript技巧

vue3 绑定多个model技巧之 抽取useVModel

Python编码解码技巧汇总

PyCharm2021使用教程 ---9、PyCharm中的搜索技巧（文件/函数/内容）

灵活运用CSS开发技巧(66个实用技巧，值得收藏)

fetch()函数使用的一些技巧

PMP考试技巧(必备)关键词篇

typescript 技巧学习

webStorm 开发技巧

SQL 多条件查询技巧

reduce使用技巧

标签