Fibonacci sequence is a recursive sequence that depends on the following definition:
Fib(N) = Fib(N-1) + Fib(N-2)
Fib(0) = 0
Fib(1) = 1
In this problem you have to calculate this simple function. Given N, you have to calculate Fib(N) modulo 1000000007.
Input contains a single line, N (1 ≤ N ≤ 109 ).#include <bits/stdc++.h> using namespace std;
#define pb push_back #define MX 1e18 #define mod 1000000009 #define ff first #define ss second #define MAX_N 2 typedef long long ll; const ll MATMOD = 1000000007; struct Matrix{ ll mat[MAX_N][MAX_N]; int row , col; Matrix(){ row = MAX_N; col = MAX_N; init(); }; Matrix(int r,int c){ row = r; col = c; init(); } void init(){ memset(mat,0,sizeof mat); } void identity(){ for(int i=0;i<row;i++)mat[i][i] = 1; } void printMatrix(){ for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ cout<<mat[i][j]<<" "; }cout<<endl; } } void getMatrix(){ for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ scanf("%d",&mat[i][j]); } } } }; Matrix matMul(Matrix a, Matrix b){ Matrix c ; for(int i=0;i<MAX_N;i++){ for(int j=0;j<MAX_N;j++){ for(int k=0;k<MAX_N;k++){ c.mat[i][j] = (c.mat[i][j] + (a.mat[i][k] * b.mat[k][j])%MATMOD )%MATMOD; } } } return c; } Matrix matPow(Matrix A, ll p){ Matrix res; res.identity(); while(p){ if(p & 1)res = matMul(res,A); A = matMul(A, A); p >>= 1; } return res; } int main(int argc, char const *argv[]) { Matrix A,C; Matrix x; A.mat[0][0] = 0; A.mat[0][1] = 1; A.mat[1][0] = 1; A.mat[1][1] = 1; C.mat[0][0] = 0; C.mat[1][0] = 1; int n; scanf("%d", &n); x = matPow(A,n); x = matMul(x,C); printf("%lld\n", x.mat[0][0]); return 0; }
