fork download
copy 
  1. #include <iostream>
  2.  
  3. typedef long long ll;
  4.  
  5. const ll mod = ll(1e9)+7;
  6.  
  7. struct Vector {
  8.     ll a, b;
  9. };
  10.  
  11. struct Matrix {
  12.     ll a, b, c, d;
  13.  
  14.     Matrix mul(const Matrix& m) const {
  15.         return Matrix{
  16.             (a * m.a + b * m.c) % mod, (a * m.b + b * m.d) % mod,
  17.             (c * m.a + d * m.c) % mod, (c * m.b + d * m.d) % mod
  18.         };
  19.     }
  20.  
  21.     Vector mul(const Vector& v) const {
  22.         return Vector{
  23.             (a * v.a + b * v.b) % mod, 
  24.             (c * v.a + d * v.b) % mod
  25.         };
  26.     }
  27. };
  28.  
  29. Matrix pow(Matrix a, ll n) {
  30.     Matrix res{1,0,0,1};
  31.     while (n > 0) {
  32.         if (n % 2 == 1) {
  33.             res = res.mul(a);
  34.         }
  35.         a = a.mul(a);
  36.         n /= 2;
  37.     }
  38.     return res;
  39. }
  40.  
  41. int main() {
  42.     Matrix A{3,1,1,3};
  43.     Vector x{1,0};
  44.     ll n;
  45.     std::cin >> n;
  46.     x = pow(A, n).mul(x);
  47.     std::cout << x.a;
  48.     return 0;
  49. }
Success #stdin #stdout 0s 4512KB
comments (?)
stdin
copy 
2
stdout
copy 
10
https://ideone.com/V6Ixxu
language:
C++14 (gcc 8.3)
created:
7 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!