fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FNAME "CANDY"
  3. using namespace std;
  4. const int MAXN = 501;
  5. typedef long long ll;
  6. const int MOD = 1e9 + 7;
  7.  
  8. void fastip() {
  9.     ios_base::sync_with_stdio(0);
  10.     cin.tie(0); cout.tie(0);
  11.     if (fopen(FNAME".inp", "r")) {
  12.         freopen(FNAME".inp", "r", stdin);
  13.         freopen(FNAME".out", "w", stdout);
  14.     }
  15. }
  16.  
  17. long long n;
  18.  
  19. struct Matrix{
  20.     int n, m;
  21.     vector<vector<long long>> f;
  22.  
  23.     Matrix(int N, int M){
  24.         n = N, m = M;
  25.         if(n > 0 && m > 0){
  26.             f.resize(n, vector<long long>(m , 0));
  27.         }
  28.     }
  29.  
  30.     void toUnit(){
  31.         for(int i = 0; i < n ; i++){
  32.             f[i][i] = 1;
  33.         }
  34.     }
  35.  
  36.     Matrix operator * (const Matrix &other) const {
  37.         Matrix res(n , other.m);
  38.         for(int i = 0; i < n ; i++){
  39.             for(int j = 0; j < other.m ; j++){
  40.                 long long total = 0;
  41.                 for(int k = 0; k < m ; k++){
  42.                     total = (total % MOD + (f[i][k] % MOD * other.f[k][j] % MOD) % MOD) % MOD;
  43.                 }
  44.                 res.f[i][j] = total % MOD;
  45.             }
  46.         }
  47.         return res;
  48.     };
  49. };
  50.  
  51. Matrix UnitMatrix(3, 3);
  52.  
  53. Matrix Pow(Matrix t, long long exp){
  54.     if(!exp){
  55.         return UnitMatrix;
  56.     }
  57.     Matrix tmp = Pow(t, exp / 2);
  58.     if(exp % 2 == 0) return tmp * tmp;
  59.     return tmp * tmp * t;
  60. }
  61.  
  62. int main(){
  63.     fastip();
  64.     UnitMatrix.toUnit();
  65.  
  66.     cin >> n;
  67.  
  68.     Matrix T(3, 3);
  69.     T.f = {
  70.         {1, 1, 0},
  71.         {1, 0, 0},
  72.         {0, 1, 0}
  73.     };
  74.  
  75.     Matrix dp(3, 1);
  76.     dp.f = {
  77.         {2},
  78.         {1},
  79.         {1}
  80.     };
  81.  
  82.     Matrix res = Pow(T, n - 2) * dp;
  83.  
  84.     cout << res.f[0][0];
  85.  
  86.     return 0;
  87. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5
https://ideone.com/vL6nH6
language:
C++ (gcc 8.3)
created:
6 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!