fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. const ll mod = 1e9 + 7;
  6.  
  7. struct mat {
  8.   vector<vector<ll>> m;
  9.   ll sz;
  10.  
  11.   mat(ll _sz = 2, ll v = 0) {
  12.     sz = _sz;
  13.     m = vector<vector<ll>> (sz, vector<ll> (sz, v));
  14.   }
  15.  
  16.   mat(vector<vector<ll>> _m) {
  17.     m = _m;
  18.   }
  19.  
  20.   vector<ll>& operator[](size_t x) {
  21.     return m[x];
  22.   }
  23.  
  24.   friend mat operator+(mat& a, mat& b) {
  25.     mat res(a.m);
  26.     for (int i = 0 ; i < a.sz ; i ++) {
  27.       for (int j = 0 ; j < a.sz ; j ++) {
  28.         res[i][j] += b[i][j];
  29.         if (res[i][j] >= mod) res[i][j] -= mod;
  30.       }
  31.     }
  32.     return res;
  33.   }
  34.  
  35.   friend mat operator*(mat& a, mat& b) {
  36.     mat res(a.sz);
  37.     for (int i = 0 ; i < a.sz ; i ++) {
  38.       for (int j = 0 ; j < a.sz ; j ++) {
  39.         for (int k = 0 ; k < a.sz ; k  ++) {
  40.           (res.m[i][j] += a.m[i][k] * b.m[k][j] % mod) %= mod;
  41.         }
  42.       }
  43.     }
  44.     return res;
  45.   }
  46.   inline void operator*=(mat& b) {
  47.     mat res(sz);
  48.     for (int i = 0 ; i < sz ; i ++) {
  49.       for (int j = 0 ; j < sz ; j ++) {
  50.         for (int k = 0 ; k < sz ; k  ++) {
  51.           (res.m[i][j] += m[i][k] * b.m[k][j] % mod) %= mod;
  52.         }
  53.       }
  54.     }
  55.     m.swap(res.m);
  56.   }
  57.  
  58. };
  59.  
  60. inline mat pw(mat& a, ll b) {
  61.   if (b == 0) return mat();
  62.   mat res = a;
  63.   for (b -- ; b ; b >>= 1, a *= a) {
  64.     if (b & 1) res *= a;
  65.   }
  66.   return res;
  67. }
  68.  
  69. int main() {
  70.  
  71. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EYkUS2
language:
C++14 (gcc 8.3)
created:
68 days 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!