Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- typedef long long ll;
- typedef vector<vector<int>> matrix;
- typedef vector<vector<double>> d_matrix;
- const int maxn = 1e5 + 10;
- const int INF = 2e9;
- const ll MOD = 998244353;
- void print(matrix A) {
- int n = (int) A.size(), m = (int) A[0].size();
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- cout << A[i][j] << " ";
- }
- cout << endl;
- }
- cout << endl;
- }
- void print(d_matrix A) {
- int n = (int) A.size(), m = (int) A[0].size();
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- cout << A[i][j] << " ";
- }
- cout << endl;
- }
- cout << endl;
- }
- matrix multiply_by_k(matrix A, int k) {
- matrix res = A;
- int n = (int) A.size(), m = (int) A[0].size();
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- res[i][j] *= k;
- }
- }
- return res;
- }
- matrix add_two_matrices(matrix A, matrix B) {
- int n_a = (int) A.size(), m_a = (int) A[0].size();
- int n_b = (int) B.size(), m_b = (int) B[0].size();
- if(n_a == n_b and m_a == m_b) {
- matrix res = A;
- for(int i = 0; i < n_a; i++) {
- for(int j = 0; j < m_a; j++) {
- res[i][j] = A[i][j] + B[i][j];
- }
- }
- return res;
- }
- cout << "Dimenziite na matricite treba da se isti za da mozhe da gi sobereme istite" << endl;
- return {{0}};
- }
- matrix subtract_two_matrices(matrix A, matrix B) {
- int n_a = (int) A.size(), m_a = (int) A[0].size();
- int n_b = (int) B.size(), m_b = (int) B[0].size();
- if(n_a != n_b or m_a != m_b) {
- cout << "Dimenziite na matricite treba da se isti za da mozhe da gi sobereme istite" << endl;
- return {{0}};
- }
- matrix res = A;
- for(int i = 0; i < n_a; i++) {
- for(int j = 0; j < m_a; j++) {
- res[i][j] = A[i][j] - B[i][j];
- }
- }
- return res;
- }
- matrix multiply_two_matrices(matrix A, matrix B) {
- int n_a = (int) A.size(), m_a = (int) A[0].size();
- int n_b = (int) B.size(), m_b = (int) B[0].size();
- if(m_a != n_b) {
- cout << "Matricite ne mozhat da se mnozhat" << endl;
- return {{0}};
- }
- matrix res(n_a, vector<int>(m_b, 0));
- for(int i = 0; i < n_a; i++) {
- for(int j = 0; j < m_b; j++) {
- int c = 0;
- for(int k = 0; k < n_a; k++) {
- c += (A[i][k] * B[k][j]) % MOD;
- c %= MOD;
- }
- res[i][j] = c % MOD;
- }
- }
- return res;
- }
- int determinant_of_matrix(matrix A) {
- int sz = (int) A.size();
- if(sz == 2) {
- return (A[0][0] * A[1][1]) - (A[0][1] * A[1][0]);
- }
- int determinant = 0;
- int sign = 1;
- for(int i = 0; i < sz; i++) {
- int n = 0, m = 0;
- matrix tmp(sz - 1, vector<int>(sz - 1, 0));
- for(int j = 0; j < sz; j++) {
- for(int k = 0; k < sz; k++) {
- if(j != 0 and k != i) {
- tmp[n][m] = A[j][k];
- if(m < sz - 2) {
- m++;
- }
- else {
- m = 0;
- n++;
- }
- }
- }
- }
- determinant = determinant + sign*(A[0][i]) * determinant_of_matrix(tmp);
- sign *= -1;
- }
- return determinant;
- }
- matrix transpose_matrix(matrix A) {
- int n = (int) A.size();
- int m = (int) A[0].size();
- matrix res(m, vector<int>(n));
- for(int j = 0; j < m; j++) {
- for(int i = 0; i < n; i++) {
- res[j][i] = A[i][j];
- }
- }
- return res;
- }
- d_matrix inverse_of_matrix(matrix A) {
- int n = (int) A.size();
- int m = (int) A[0].size();
- d_matrix res(n, vector<double>(m));
- matrix adj_matrix(n, vector<int>(m));
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- matrix minor(n - 1, vector<int>(m - 1));
- int r = 0, c = 0;
- for(int a = 0; a < n; a++) {
- if(a == i) continue;
- for(int b = 0; b < m; b++) {
- if(a == i or b == j) continue;
- minor[r][c] = A[a][b];
- c++;
- }
- c = 0;
- r++;
- }
- adj_matrix[i][j] = determinant_of_matrix(minor);
- if((i + j) % 2 == 1) {
- adj_matrix[i][j] *= -1;
- }
- }
- }
- adj_matrix = transpose_matrix(adj_matrix);
- double det = determinant_of_matrix(A);
- cout << det << endl;
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- res[i][j] = (1.0 / det) * adj_matrix[i][j];
- }
- }
- return res;
- }
- ll power(ll a, ll b) {
- ll res = 1;
- while(b) {
- if(b % 2 == 1) {
- res *= a;
- }
- a *= a;
- b /= 2;
- }
- return res;
- }
- ll nth_fibbonaci_number(ll x) {
- matrix A = {
- {1, 1},
- {1, 0}
- };
- matrix B = A;
- // for(int i = 0; i < x; i++) {
- // A = multiply_two_matrices(A, B);
- // }
- matrix res = {
- {1, 0},
- {0, 1}
- };
- while(x) {
- if(x % 2 == 1) {
- res = multiply_two_matrices(res, A);
- }
- A = multiply_two_matrices(A, A);
- x /= 2;
- }
- return res[0][0];
- }
- int main() {
- // nth_fibbonaci_number(8);
- // return 0;
- for(int i = 1; i <= 10; i++) {
- cout << nth_fibbonaci_number(i) << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement