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).
The input test file will contain a single line containing n (n ≤ 100). There are multiple test cases!
For each test case, PRint the Fn mod (10^9 + 7).
9
34
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).
The input test file will contain a single line containing n (n ≤ 2^31-1). There are multiple test cases!
For each test case, ple Input 9
34
You may need to use “long long”.
#include <cmath>#include <cstring>using namespace std;#define MOD 1000000007struct matrix{ long long a[2][2];};matrix mul(matrix x,matrix y){ matrix m; memset(m.a,0,sizeof(m.a)); for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) m.a[i][j]=(m.a[i][j]+x.a[i][k]*y.a[k][j])%MOD; return m;}void power(int n){ matrix t,result; t.a[0][0]=1; t.a[0][1]=1; t.a[1][0]=1; t.a[1][1]=0; memset(result.a,0,sizeof(result.a)); for(int i=0;i<2;i++) result.a[i][i]=1; while(n) { if(n&1) result=mul(result,t); t=mul(t,t); n=n>>1; } cout << result.a[0][1] << endl;}int main(){ int n; while(cin>>n) { power(n); } return 0;}新聞熱點
疑難解答
