API tools faq
paste
Advertisement
Abrar_Al_Samit

Matrix Template

Abrar_Al_Samit
Jan 6th, 2023
1,022
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.98 KB | None | 0 0
raw download clone embed print report
  1. class matrix {
  2. public:
  3.     matrix() {
  4.         rows_ = columns_ = 0;
  5.     }
  6.  
  7.     matrix(int n, int m): rows_(n), columns_(m) {
  8.         memset(v, 0, sizeof(v));
  9.     }
  10.  
  11.     int rows() const {
  12.         return rows_;
  13.     }
  14.  
  15.     int columns() const {
  16.         return columns_;
  17.     }
  18.  
  19.     matrix transpose() const {
  20.         matrix res(columns(), rows());
  21.         for (int i = 0; i < rows(); ++i) {
  22.             for (int j = 0; j < columns(); ++j) {
  23.                 res[j][i] = v[i][j];
  24.             }
  25.         }
  26.         return res;
  27.     }
  28.  
  29.     matrix operator + (const matrix &m) const {
  30.         matrix res(rows(), columns());
  31.         for (int i = 0; i < rows(); ++i) {
  32.             for (int j = 0; j < columns(); ++j) {
  33.                 res[i][j] = v[i][j] + m[i][j];
  34.                 if (res[i][j] >= mod) {
  35.                     res[i][j] -= mod;
  36.                 }
  37.             }
  38.         }
  39.         return res;
  40.     }
  41.  
  42.     matrix operator * (const matrix &m) const {
  43.         matrix res(rows(), m.columns());
  44.         matrix t = m.transpose();
  45.         for (int i = 0; i < res.rows(); ++i) {
  46.             for (int j = 0; j < res.columns(); ++j) {
  47.                 const int *first = v[i];
  48.                 const int *second = t[j];
  49.                 unsigned long long sum = 0;
  50.                 int it = 0;
  51.                 for (int k = 0; k < columns(); ++k) {
  52.                     sum += 1LLU * (*first) * (*second);
  53.                     ++first;
  54.                     ++second;
  55.                     ++it;
  56.                     if (it == 18) {
  57.                         sum %= mod;
  58.                         it = 0;
  59.                     }
  60.                 }
  61.                 res.v[i][j] = sum % mod;
  62.             }
  63.         }
  64.         return res;
  65.     }
  66.  
  67.     int* operator [] (int row) {
  68.         return v[row];
  69.     }
  70.  
  71.     const int* operator [] (int row) const {
  72.         return v[row];
  73.     }
  74.  
  75.     bool operator == (const matrix &m) const {
  76.         if (rows() == m.rows() && columns() == m.columns()) {
  77.             for (int i = 0; i < rows(); ++i) {
  78.                 for (int j = 0; j < columns(); ++j) {
  79.                     if (v[i][j] != m[i][j]) {
  80.                         return false;
  81.                     }
  82.                 }
  83.             }
  84.             return true;
  85.         }
  86.         return false;
  87.     }
  88.  
  89.     friend ostream &operator << (ostream &os, const matrix &m) {
  90.         for (int i = 0; i < m.rows(); ++i) {
  91.             for (int j = 0; j < m.columns(); ++j) {
  92.                 os << m[i][j] << " ";
  93.             }
  94.             os << "\n";
  95.         }
  96.         return os;
  97.     }
  98.  
  99. private:
  100.     int v[max_n][max_n];
  101.     int rows_, columns_;
  102. };
  103.  
  104. matrix power(const matrix &a, long long b) {
  105.     if (b == 0) {
  106.         matrix res(a.rows(), a.columns());
  107.         for (int i = 0; i < res.rows(); ++i) {
  108.             res[i][i] = 1;
  109.         }
  110.         return res;
  111.     }
  112.     if (b % 2 == 0) {
  113.         return power(a * a, b / 2);
  114.     }
  115.     return a * power(a, b - 1);
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!