fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define MAX 100005
  4. #define MOD 1000000007
  5. using namespace std;
  6.  
  7. vector <vector <ll> > m(vector <vector <ll> > a, vector <vector <ll> > b, int Size){
  8.  
  9.     vector <vector <ll> > c(Size, vector<ll>(Size, 0));
  10.  
  11.     for(int i=0; i<Size; i++){
  12.         for(int j=0; j<Size; j++){
  13.             for(int k=0; k<Size; k++){
  14.                 c[i][j] += a[i][k]*b[k][j];
  15.                 c[i][j] %= MOD;
  16.             }
  17.         }
  18.     }
  19.  
  20.     return c;
  21. }
  22.  
  23. vector <vector <ll> > power(vector <vector <ll> > a, int n, int Size){
  24.  
  25.     vector <vector <ll> > b(Size, vector<ll>(Size, 0));
  26.     for(int i=0; i<Size; i++){   // let b = identity matrix
  27.         b[i][i] = 1;
  28.     }
  29.  
  30.     string s;
  31.  
  32.     while(n>=1){
  33.         if(n%2){
  34.             s += '1';
  35.         }else{
  36.             s += '0';
  37.         }
  38.  
  39.         n /= 2;
  40.     }
  41.  
  42.  
  43.  
  44.     for(int i=0; i<s.size(); i++){
  45.         if(s[i]=='1'){
  46.             b = m(a, b, 2);
  47.         }
  48.  
  49.         a = m(a, a, 2);
  50.     }
  51.  
  52.     return b;
  53. }
  54.  
  55. int main(){
  56.  
  57.  
  58.     vector <vector <ll> > a(2, vector<ll>(2, 0));
  59.     a[0][1] = a[1][0] = a[1][1] = 1;
  60.  
  61.     int n;
  62.     cin >> n;
  63.     cout << power(a, n, 2)[1][1] << endl;
  64. }
  65.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
10
stdout
copy 
89
https://ideone.com/RL0cBg
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!