51Nod-1242 斐波那契数列的第n项

本文主要是介绍51Nod-1242 斐波那契数列的第n项，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1242 斐波那契数列的第N项 

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题

斐波那契数列的定义如下：

F(0) = 0

F(1) = 1

F(n) = F(n - 1) + F(n - 2) (n >= 2)

(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...)

给出n，求F(n)，由于结果很大，输出F(n) % 1000000009的结果即可。

Input

输入1个数n(1 <= n <= 10^18)。

Output

输出F(n) % 1000000009的结果。

Input示例

11

Output示例

89

斐波那契数列求第n项（当n非常大时），利用矩阵快速幂计算是fefe非常迅速的

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
#define LL long longconst LL INF = 1000000009;LL n;struct Node {LL c[2][2];
} t;Node mult(Node a, Node b) {Node c = {0};for(int i = 0; i < 2; i++)for(int j = 0; j < 2; j++)for(int k = 0; k < 2; k++) {c.c[i][j] += (a.c[i][k] * b.c[k][j]) % INF;c.c[i][j] %= INF;}return c;
}Node pow(LL n) {Node pt = t;if(n < 0) return pt;while(n) {if( n & 1 ) {pt = mult(pt, t);n--;}t = mult(t, t);n = n >> 1;}return pt;
}int main() {while(cin>>n) {t.c[0][0] = 1;t.c[0][1] = 1;t.c[1][0] = 1;t.c[1][1] = 0;Node ans = pow(n-2);printf("%lld\n", ans.c[0][0] * 1);}return 0;
}

 

这篇关于51Nod-1242 斐波那契数列的第n项的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---