fork download 
  1. /**
  2.  https://v...content-available-to-author-only...e.net/problem/Gym-102644C
  3.  Date: 2023-07-31
  4.  Author: Kawchar85
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define endl "\n"
  11. #define MOD 1000000007
  12. #define MAX 200005
  13.  
  14. typedef long long ll;
  15.  
  16. struct matrix {
  17.     int n, m;
  18.     vector<vector<int>> v;
  19.     matrix() {}
  20.     matrix(int _n, int _m) {
  21.         n = _n; m = _m;
  22.         v.assign(n, vector<int>(m, 0));
  23.     }
  24.     matrix(vector<vector<int>> _v) {
  25.         n = _v.size(); 
  26.         m = n ? _v[0].size() : 0;
  27.         v = _v;
  28.     }
  29.     void make_unit() {
  30.         assert(n == m);
  31.         for(int i = 0; i < n; i++)
  32.             for(int j = 0; j < m; j++)
  33.                 v[i][j] = (i==j);
  34.     }
  35.     matrix operator + (const matrix &a) {
  36.         assert(n == a.n && m == a.m);
  37.         matrix ans = matrix(n, m);
  38.         for(int i = 0; i < n; i++) {
  39.             for(int j = 0; j < m; j++) {
  40.             ans.v[i][j] = (v[i][j] + a.v[i][j]) % MOD;
  41.           }
  42.         }
  43.         return ans;
  44.     }
  45.     matrix operator - (const matrix &a) {
  46.         assert(n == a.n && m == a.m);
  47.         matrix ans = matrix(n, m);
  48.         for(int i = 0; i < n; i++) {
  49.             for(int j = 0; j < m; j++) {
  50.                 ans.v[i][j] = (v[i][j] - a.v[i][j] + MOD) % MOD;
  51.             }
  52.         }
  53.         return ans;
  54.     }
  55.     matrix operator * (const matrix &a) {
  56.         assert(m == a.n);
  57.         matrix ans = matrix(n, a.m);
  58.         for(int i = 0; i < n; i++) {
  59.             for(int j = 0; j < a.m; j++) {
  60.                 for(int k = 0; k < m; k++) {
  61.                     ans.v[i][j] = (ans.v[i][j] + 1LL * v[i][k] * a.v[k][j] % MOD) % MOD;
  62.                 }
  63.             }
  64.         }
  65.         return ans;
  66.     }
  67.  
  68.     matrix pow(long long k) {
  69.         assert(n == m);
  70.         matrix ans(n, n), t = v;
  71.         ans.make_unit();
  72.         while(k) {
  73.             if(k&1) ans = ans * t;
  74.             t = t * t;
  75.             k >>= 1;
  76.         }
  77.         return ans;
  78.     }
  79.  
  80.     void print() {
  81.         for(int i = 0; i < n; i++)
  82.             for(int j = 0; j < m; j++)
  83.                 cout << v[i][j] << " \n"[j+1 == m];
  84.     }
  85.  
  86.     matrix& operator += (const matrix& b) { return *this = (*this) + b; }
  87.     matrix& operator -= (const matrix& b) { return *this = (*this) - b; }
  88.     matrix& operator *= (const matrix& b) { return *this = (*this) * b; }
  89.     bool operator == (const matrix& b) { return v == b.v; }
  90.     bool operator != (const matrix& b) { return v != b.v; }
  91.  
  92. };
  93.  
  94. void solve() {
  95.     ll n; cin >> n;
  96.  
  97.     matrix a(2, 2);
  98.     a.v[0][0] = 1;
  99.     a.v[0][1] = 1;
  100.     a.v[1][0] = 1;
  101.     a.v[1][1] = 0;
  102.  
  103.     matrix ans = a.pow(n);
  104.     // ans.print();
  105.     cout << ans.v[0][1] << endl;
  106. }
  107.  
  108. int32_t main() {
  109.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  110.  
  111.     int TC = 1;
  112.  
  113.     //cin>>TC;
  114.  
  115.     for(int cs = 1; cs <= TC; cs++) {
  116.         //cout << "Case " << cs << ": ";
  117.         solve();
  118.     }
  119.  
  120.     return 0;
  121. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
50
stdout 
586268941
https://ideone.com/YvFyml
language:
C++14 (gcc 8.3)
created:
24 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!