mickypinata

FORCE-T0166E: Tetrahedron

Sep 2nd, 2021 (edited)
1,275
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5. typedef vector<int> vi;
  6. typedef vector<vector<int>> vvi;
  7.  
  8. const int N = 1e7;
  9. const int logN = log2(N);
  10. const int MD = 1e9 + 7;
  11.  
  12. vvi bl[logN];
  13.  
  14. vvi matMultiply(vvi a, vvi b){
  15.     int l = a.size();
  16.     int m = a[0].size();
  17.     int r = b[0].size();
  18.     vvi ans(l, vi(r, 0));
  19.     for(int i = 0; i < l; ++i){
  20.         for(int j = 0; j < r; ++j){
  21.             for(int k = 0; k < m; ++k){
  22.                 ans[i][j] = (ans[i][j] + (lli)a[i][k] * b[k][j]) % MD;
  23.             }
  24.         }
  25.     }
  26.     return ans;
  27. }
  28.  
  29. int main(){
  30.  
  31.     int x;
  32.     scanf("%d", &x);
  33.     bl[0] = {{0, 1}, {3, 2}};
  34.     for(int i = 1; i <= logN; ++i){
  35.         bl[i] = matMultiply(bl[i - 1], bl[i - 1]);
  36.     }
  37.     vvi ans = {{1}, {0}};
  38.     for(int i = logN; i >= 0; --i){
  39.         if(x >= (1 << i)){
  40.             ans = matMultiply(bl[i], ans);
  41.             x -= (1 << i);
  42.         }
  43.     }
  44.     cout << ans[0][0];
  45.  
  46.     return 0;
  47. }
  48.  
RAW Paste Data Copied