首页 > 其他 > 详细

[洛谷1962]斐波那契数列

时间:2017-08-15 09:12:56      阅读:218      评论:0      收藏:0      [点我收藏+]

思路:

常见算法时矩阵快速幂,但事实上这题可以不需要矩阵快速幂。
设斐波那契数列为$f$,观察规律可以发现:
当$n$为偶数时,$f_n=(f_{n-1}\times 2+f_n)\times f_n$;
当$m$为奇数时,$f_n=f_{n+1}^2+f_n^2$。
这样只要用一个map记录已经计算过的Fibonacci数,递归求得答案即可。
再用一个hash_map跑得和标算一样快(0ms),而且内存更小。

 1 #include<cstdio>
 2 #include<ext/hash_map>
 3 const long long mod=1000000007;
 4 __gnu_cxx::hash_map<int,int> m;
 5 inline long long sqr(const long long x) {
 6     return x*x;
 7 }
 8 long long Fibonacci(const long long n) {
 9     if(m[n]) return m[n];
10     if(n==1||n==2) return m[n]=1;
11     if(n&1) return m[n]=(sqr(Fibonacci(n/2+1))+sqr(Fibonacci(n/2)))%mod;
12     return m[n]=(Fibonacci(n/2-1)*2+Fibonacci(n/2))*Fibonacci(n/2)%mod;
13 }
14 int main() {
15     long long n;
16     scanf("%lld",&n);
17     printf("%lld",Fibonacci(n));
18     return 0;
19 }

 

[洛谷1962]斐波那契数列

原文:http://www.cnblogs.com/skylee03/p/7363190.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!