Advertisement
Josif_tepe

Untitled

Apr 18th, 2024
759
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. typedef long long ll;
  6. typedef vector<vector<ll>> matrix;
  7. typedef vector<vector<double>> d_matrix;
  8. const int maxn = 1e5 + 10;
  9. const int INF = 2e9;
  10. const ll MOD = 100000007;
  11.  
  12. class StairsToRazorTower
  13. {
  14. public:
  15.     matrix multiply_two_matrices(matrix A, matrix B) {
  16.         int n_a = (int) A.size(), m_a = (int) A[0].size();
  17.         int n_b = (int) B.size(), m_b = (int) B[0].size();
  18.        
  19.         if(m_a != n_b) {
  20.             return {{0}};
  21.         }
  22.         matrix res(n_a, vector<ll>(m_b, 0));
  23.         for(int i = 0; i < n_a; i++) {
  24.             for(int j = 0; j < m_b; j++) {
  25.                 ll c = 0;
  26.                 for(int k = 0; k < n_a; k++) {
  27.                     c += (A[i][k] * B[k][j]) % MOD;
  28.                     c %= MOD;
  29.                 }
  30.                 res[i][j] = c % MOD;
  31.             }
  32.         }
  33.        
  34.         return res;
  35.     }
  36.     ll nth_fibbonaci_number(ll x) {
  37.         matrix A = {
  38.             {1, 0, 1},
  39.             {1, 0, 0},
  40.             {0, 1, 0}
  41.         };
  42.         matrix B = A;
  43.     //    for(int i = 0; i < x; i++) {
  44.     //        A = multiply_two_matrices(A, B);
  45.     //    }
  46.         matrix res = {
  47.             {1, 0, 0,},
  48.             {0, 1, 0},
  49.             {0, 0, 1}
  50.         };
  51.         while(x) {
  52.             if(x % 2 == 1) {
  53.                 res = multiply_two_matrices(res, A);
  54.             }
  55.             A = multiply_two_matrices(A, A);
  56.             x /= 2;
  57.         }
  58.        
  59.         return res[0][0];
  60.     }
  61.     ll getNumberOfWays( ll n )
  62.     {
  63.         return nth_fibbonaci_number(n);
  64.     }
  65. };
  66. int main() {
  67. //    nth_fibbonaci_number(8);
  68. //    return 0;
  69.     StairsToRazorTower s;
  70.    
  71.     for(int i = 1; i <= 10; i++) {
  72.         cout << s.getNumberOfWays(969710026) << " ";
  73.     }
  74.     return 0;
  75. }
  76.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement