首页 > 代码库 > sicily 1001. Fibonacci 2
sicily 1001. Fibonacci 2
1001. Fibonacci 2
Description
In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn-1 + Fn-2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Given an integer n, your goal is to compute the last Fn mod (10^9 + 7).
Input
The input test file will contain a single line containing n (n ≤ 2^31-1).
There are multiple test cases!
Output
For each test case, print the Fn mod (10^9 + 7).
Sample Input
Copy sample input to clipboard 9
Sample Output
34
用矩阵快速幂的方法，具体可见： http://blog.csdn.net/ACdreamers/article/details/25616461
#include <iostream>using namespace std;#define M 1000000007struct Matrix{ long long v[2][2];};Matrix matrixMul(Matrix a, Matrix b) { Matrix temp; for (int i = 0; i != 2; i++) { for (int j = 0; j != 2; j++) { temp.v[i][j] = 0; for (int k = 0; k != 2; k++) { temp.v[i][j] += a.v[i][k] * b.v[k][j]; temp.v[i][j] %= M; } } } return temp;}Matrix power(Matrix a, Matrix b, long long n) { while (n) { if (n & 1) { b = matrixMul(b, a); } n >>= 1; a = matrixMul(a, a); } return b;}int main(int argc, char* argv[]) { Matrix a = {1, 1, 1, 0}, b = {1, 0, 0, 1}; long long n; while (cin >> n) { if (n == 0) cout << 0 << endl; else { Matrix result = power(a, b, n - 1); cout << result.v[0][0] << endl; } } return 0;}
sicily 1001. Fibonacci 2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。