fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const long long mod = 1e9+7;
  6.  
  7. using type = long long;
  8.  
  9. struct Matrix {
  10.     vector <vector <type> > data;
  11.  
  12.     long long row() const { return data.size(); }
  13.  
  14.     long long col() const { return data[0].size(); }
  15.  
  16.     auto & operator [] (long long i) { return data[i]; }
  17.  
  18.     const auto & operator[] (long long i) const { return data[i]; }
  19.  
  20.     Matrix() = default;
  21.  
  22.     Matrix(long long r, long long c): data(r, vector <type> (c)) { }
  23.  
  24.     Matrix(const vector <vector <type> > &d): data(d) { }
  25.  
  26.     friend ostream & operator << (ostream &out, const Matrix &d) {
  27.         for (auto x : d.data) {
  28.             for (auto y : x) out << y << ' ';
  29.             out << '\n';
  30.         }
  31.         return out;
  32.     }
  33.  
  34.     static Matrix identity(long long n) {
  35.         Matrix a = Matrix(n, n);
  36.         while (n--) a[n][n] = 1;
  37.         return a;
  38.     }
  39.  
  40.     Matrix operator * (const Matrix &b) {
  41.         Matrix a = *this;
  42.         assert(a.col() == b.row());
  43.         Matrix c(a.row(), b.col());
  44.         for (long long i = 0; i < a.row(); ++i)
  45.             for (long long j = 0; j < b.col(); ++j)
  46.                 for (long long k = 0; k < a.col(); ++k){
  47.                     c[i][j] += 1ll * a[i][k] % mod * (b[k][j] % mod) % mod;
  48.                     c[i][j] %= mod;
  49.                 }
  50.         return c;
  51.     }
  52.  
  53.     Matrix pow(long long exp) {
  54.         assert(row() == col());
  55.         Matrix base = *this, ans = identity(row());
  56.         for (; exp > 0; exp >>= 1, base = base * base)
  57.             if (exp & 1) ans = ans * base;
  58.         return ans;
  59.     }
  60. };
  61.  
  62. signed main(){
  63.     Matrix a({
  64.         {1, 1},
  65.         {1, 0}
  66.     });
  67.  
  68.  
  69.     long long n;
  70.     cin >> n;
  71.     Matrix tmp = a.pow(n - 2);
  72.     cout << (tmp[0][0] + tmp[0][1]) % mod << '\n';
  73. }
  74.  
Success #stdin #stdout 0.01s 5476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
653530764
https://ideone.com/ip0ruA
language:
C++14 (clang 8.0)
created:
1 year ago
visibility:
secret

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!