Advertisement
Josif_tepe

Untitled

Apr 18th, 2024
751
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.73 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<int>> matrix;
  7. typedef vector<vector<double>> d_matrix;
  8. const int maxn = 1e5 + 10;
  9. const int INF = 2e9;
  10. const ll MOD = 998244353;
  11. void print(matrix A) {
  12.     int n = (int) A.size(), m = (int) A[0].size();
  13.     for(int i = 0; i < n; i++) {
  14.         for(int j = 0; j < m; j++) {
  15.             cout << A[i][j] << " ";
  16.         }
  17.         cout << endl;
  18.     }
  19.     cout << endl;
  20. }
  21. void print(d_matrix A) {
  22.     int n = (int) A.size(), m = (int) A[0].size();
  23.     for(int i = 0; i < n; i++) {
  24.         for(int j = 0; j < m; j++) {
  25.             cout << A[i][j] << " ";
  26.         }
  27.         cout << endl;
  28.     }
  29.     cout << endl;
  30. }
  31. matrix multiply_by_k(matrix A, int k) {
  32.     matrix res = A;
  33.     int n = (int) A.size(), m = (int) A[0].size();
  34.    
  35.     for(int i = 0; i < n; i++) {
  36.         for(int j = 0; j < m; j++) {
  37.             res[i][j] *= k;
  38.         }
  39.     }
  40.     return res;
  41. }
  42. matrix add_two_matrices(matrix A, matrix B) {
  43.     int n_a = (int) A.size(), m_a = (int) A[0].size();
  44.     int n_b = (int) B.size(), m_b = (int) B[0].size();
  45.    
  46.     if(n_a == n_b and m_a == m_b) {
  47.         matrix res = A;
  48.         for(int i = 0; i < n_a; i++) {
  49.             for(int j = 0; j < m_a; j++) {
  50.                 res[i][j] = A[i][j] + B[i][j];
  51.             }
  52.         }
  53.         return res;
  54.     }
  55.     cout << "Dimenziite na matricite treba da se isti za da mozhe da gi sobereme istite" << endl;
  56.     return {{0}};
  57. }
  58. matrix subtract_two_matrices(matrix A, matrix B) {
  59.     int n_a = (int) A.size(), m_a = (int) A[0].size();
  60.     int n_b = (int) B.size(), m_b = (int) B[0].size();
  61.    
  62.     if(n_a != n_b or m_a != m_b) {
  63.         cout << "Dimenziite na matricite treba da se isti za da mozhe da gi sobereme istite" << endl;
  64.         return {{0}};
  65.     }
  66.     matrix res = A;
  67.     for(int i = 0; i < n_a; i++) {
  68.         for(int j = 0; j < m_a; j++) {
  69.             res[i][j] = A[i][j] - B[i][j];
  70.         }
  71.     }
  72.     return res;
  73. }
  74. matrix multiply_two_matrices(matrix A, matrix B) {
  75.     int n_a = (int) A.size(), m_a = (int) A[0].size();
  76.     int n_b = (int) B.size(), m_b = (int) B[0].size();
  77.    
  78.     if(m_a != n_b) {
  79.         cout << "Matricite ne mozhat da se mnozhat" << endl;
  80.         return {{0}};
  81.     }
  82.     matrix res(n_a, vector<int>(m_b, 0));
  83.     for(int i = 0; i < n_a; i++) {
  84.         for(int j = 0; j < m_b; j++) {
  85.             int c = 0;
  86.             for(int k = 0; k < n_a; k++) {
  87.                 c += (A[i][k] * B[k][j]) % MOD;
  88.                 c %= MOD;
  89.             }
  90.             res[i][j] = c % MOD;
  91.         }
  92.     }
  93.    
  94.     return res;
  95. }
  96. int determinant_of_matrix(matrix A) {
  97.     int sz = (int) A.size();
  98.     if(sz == 2) {
  99.         return (A[0][0] * A[1][1]) - (A[0][1] * A[1][0]);
  100.     }
  101.     int determinant = 0;
  102.     int sign = 1;
  103.     for(int i = 0; i < sz; i++) {
  104.         int n = 0, m = 0;
  105.        
  106.         matrix tmp(sz - 1, vector<int>(sz - 1, 0));
  107.         for(int j = 0; j < sz; j++) {
  108.             for(int k = 0; k < sz; k++) {
  109.                 if(j != 0 and k != i) {
  110.                     tmp[n][m] = A[j][k];
  111.                     if(m < sz - 2) {
  112.                         m++;
  113.                     }
  114.                     else {
  115.                         m = 0;
  116.                         n++;
  117.                     }
  118.                 }
  119.             }
  120.            
  121.         }
  122.         determinant = determinant + sign*(A[0][i]) * determinant_of_matrix(tmp);
  123.         sign *= -1;
  124.     }
  125.     return determinant;
  126. }
  127. matrix transpose_matrix(matrix A) {
  128.     int n = (int) A.size();
  129.     int m = (int) A[0].size();
  130.     matrix res(m, vector<int>(n));
  131.    
  132.     for(int j = 0; j < m; j++) {
  133.         for(int i = 0; i < n; i++) {
  134.             res[j][i] = A[i][j];
  135.         }
  136.     }
  137.    
  138.     return res;
  139. }
  140. d_matrix inverse_of_matrix(matrix A) {
  141.     int n = (int) A.size();
  142.     int m = (int) A[0].size();
  143.     d_matrix res(n, vector<double>(m));
  144.    
  145.     matrix adj_matrix(n, vector<int>(m));
  146.    
  147.     for(int i = 0; i < n; i++) {
  148.         for(int j = 0; j < m; j++) {
  149.             matrix minor(n - 1, vector<int>(m - 1));
  150.             int r = 0, c = 0;
  151.             for(int a = 0; a < n; a++) {
  152.                 if(a == i) continue;
  153.                 for(int b = 0; b < m; b++) {
  154.                     if(a == i or b == j) continue;
  155.                     minor[r][c] = A[a][b];
  156.                     c++;
  157.                 }
  158.                 c = 0;
  159.                
  160.                 r++;
  161.             }
  162.             adj_matrix[i][j] = determinant_of_matrix(minor);
  163.             if((i + j) % 2 == 1) {
  164.                 adj_matrix[i][j] *= -1;
  165.             }
  166.         }
  167.     }
  168.     adj_matrix = transpose_matrix(adj_matrix);
  169.     double det = determinant_of_matrix(A);
  170.     cout << det << endl;
  171.     for(int i = 0; i < n; i++) {
  172.         for(int j = 0; j < m; j++) {
  173.             res[i][j] = (1.0 / det) * adj_matrix[i][j];
  174.         }
  175.     }
  176.    
  177.     return res;
  178. }
  179.  
  180.  
  181. ll power(ll a, ll b) {
  182.     ll res = 1;
  183.     while(b) {
  184.         if(b % 2 == 1) {
  185.             res *= a;
  186.         }
  187.         a *= a;
  188.         b /= 2;
  189.     }
  190.     return res;
  191. }
  192. ll nth_fibbonaci_number(ll x) {
  193.     matrix A = {
  194.         {1, 1},
  195.         {1, 0}
  196.     };
  197.     matrix B = A;
  198. //    for(int i = 0; i < x; i++) {
  199. //        A = multiply_two_matrices(A, B);
  200. //    }
  201.     matrix res = {
  202.         {1, 0},
  203.         {0, 1}
  204.     };
  205.     while(x) {
  206.         if(x % 2 == 1) {
  207.             res = multiply_two_matrices(res, A);
  208.         }
  209.         A = multiply_two_matrices(A, A);
  210.         x /= 2;
  211.     }
  212.    
  213.     return res[0][0];
  214. }
  215.  
  216. int main() {
  217. //    nth_fibbonaci_number(8);
  218. //    return 0;
  219.     for(int i = 1; i <= 10; i++) {
  220.         cout << nth_fibbonaci_number(i) << " ";
  221.     }
  222.     return 0;
  223. }
  224.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement