fork download
copy 
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <array>
  5. #include <iostream>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. const int mod = 1000000007;
  10.  
  11. struct vec{
  12.     array<int64_t, 2> v;
  13.  
  14.     vec(){}
  15.  
  16.     vec(int64_t a, int64_t b){
  17.         v[0] = a;
  18.         v[1] = b;
  19.     }
  20.  
  21.     int64_t& operator[](int index){
  22.         return v[index];
  23.     }
  24. };
  25.  
  26. struct mat{
  27.     array<vec, 2> m;
  28.  
  29.     vec& operator[](int index){
  30.         return m[index];
  31.     }
  32.  
  33.     vec operator*(vec in){
  34.         vec out;
  35.         out.v[0]  =  in.v[0] * m[0][0];
  36.         out.v[0] +=  in.v[1] * m[0][1];
  37.         out[0] %= mod;
  38.         out.v[1]  =  in.v[0] * m[1][0];
  39.         out.v[1] +=  in.v[1] * m[1][1];
  40.         out[1] %= mod;
  41.         return out;
  42.     }
  43.  
  44.     mat operator*(mat in){
  45.         mat out;
  46.         out [0] = (*this) * in[0];
  47.         out [1] = (*this) * in[1];
  48.         return out;
  49.     }
  50.  
  51.     mat pow(int64_t pwr){
  52.         mat out = {vec(1,0),vec(0,1)};
  53.         mat base = *this;
  54.         while (pwr){
  55.             if (pwr & 1){
  56.                 out = out * base;
  57.             }
  58.             base = base*base;
  59.             pwr /= 2;
  60.         }
  61.         return out;
  62.     }
  63. };
  64.  
  65.  
  66. int main() {
  67.     int64_t n;
  68.     cin >> n;
  69.  
  70.     mat one_step = {vec(1,1),vec(1,0)};
  71.     mat many_steps = one_step.pow(n-1);
  72.     vec first_ate = many_steps * vec(0,1);
  73.     vec first_hungry = many_steps * vec(1,0);
  74.  
  75.     int64_t answer = (first_ate[0] + first_hungry[0] + first_hungry[1]) % mod;
  76.     cout << answer << endl;
  77.  
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
1000000000000000000
stdout
copy 
150331332
https://ideone.com/OZH3L3
language:
C++14 (gcc 8.3)
created:
5 years 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!