This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ruthen71/rcpl
#include "data_structure/matrix.hpp"
#pragma once template <class T> struct Matrix { std::vector<std::vector<T>> A; Matrix(int N) : A(N, std::vector<T>(N, T(0))) {} Matrix(int N, int M, T val = T(0)) : A(N, std::vector<T>(M, val)) {} inline size_t size() const { return A.size(); } inline int row() const { return (int)A.size(); } inline int col() const { return (int)A[0].size(); } inline const std::vector<T> &operator[](int i) const { return A[i]; } // read inline std::vector<T> &operator[](int i) { return A[i]; } // write static Matrix E(int N) { Matrix ret(N); for (int i = 0; i < N; i++) ret[i][i] = T(1); return ret; } Matrix &operator+=(const Matrix &B) { int N = row(), M = col(); assert(N == B.row() and M == B.col()); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { (*this)[i][j] += B[i][j]; } } return (*this); } Matrix &operator-=(const Matrix &B) { int N = row(), M = col(); assert(N == B.row() and M == B.col()); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { (*this)[i][j] -= B[i][j]; } } return (*this); } Matrix &operator*=(const Matrix &B) { int N = row(), M = B.col(), L = B.row(); assert(L == col()); Matrix C(N, M); for (int i = 0; i < N; i++) { for (int k = 0; k < L; k++) { for (int j = 0; j < M; j++) { C[i][j] += (*this)[i][k] * B[k][j]; } } } A.swap(C.A); return (*this); } // A ^= k Matrix pow(long long k) { assert(row() == col()); Matrix B = Matrix::E(row()), X = (*this); while (k) { if (k & 1) B *= X; X *= X; k >>= 1; } A.swap(B.A); return (*this); } Matrix operator+(const Matrix &B) { return ((*this) += B); } Matrix operator-(const Matrix &B) { return ((*this) -= B); } Matrix operator*(const Matrix &B) { return ((*this) *= B); } friend std::ostream &operator<<(std::ostream &os, Matrix &A) { int N = A.row(), M = A.col(); for (int i = 0; i < N; i++) { os << '['; for (int j = 0; j < M; j++) os << A[i][j] << " \n"[j == M - 1]; } return (os); } Matrix &operator+=(const T &k) { int N = row(), M = col(); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) (*this)[i][j] += k; return (*this); } Matrix &operator-=(const T &k) { int N = row(), M = col(); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) (*this)[i][j] -= k; return (*this); } Matrix &operator*=(const T &k) { int N = row(), M = col(); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) (*this)[i][j] *= k; return (*this); } Matrix &operator/=(const T &k) { int N = row(), M = col(); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) (*this)[i][j] /= k; return (*this); } Matrix operator+(const T &k) { return ((*this) += k); } Matrix operator-(const T &k) { return ((*this) -= k); } Matrix operator*(const T &k) { return ((*this) *= k); } Matrix operator/(const T &k) { return ((*this) /= k); } };
#line 2 "data_structure/matrix.hpp" template <class T> struct Matrix { std::vector<std::vector<T>> A; Matrix(int N) : A(N, std::vector<T>(N, T(0))) {} Matrix(int N, int M, T val = T(0)) : A(N, std::vector<T>(M, val)) {} inline size_t size() const { return A.size(); } inline int row() const { return (int)A.size(); } inline int col() const { return (int)A[0].size(); } inline const std::vector<T> &operator[](int i) const { return A[i]; } // read inline std::vector<T> &operator[](int i) { return A[i]; } // write static Matrix E(int N) { Matrix ret(N); for (int i = 0; i < N; i++) ret[i][i] = T(1); return ret; } Matrix &operator+=(const Matrix &B) { int N = row(), M = col(); assert(N == B.row() and M == B.col()); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { (*this)[i][j] += B[i][j]; } } return (*this); } Matrix &operator-=(const Matrix &B) { int N = row(), M = col(); assert(N == B.row() and M == B.col()); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { (*this)[i][j] -= B[i][j]; } } return (*this); } Matrix &operator*=(const Matrix &B) { int N = row(), M = B.col(), L = B.row(); assert(L == col()); Matrix C(N, M); for (int i = 0; i < N; i++) { for (int k = 0; k < L; k++) { for (int j = 0; j < M; j++) { C[i][j] += (*this)[i][k] * B[k][j]; } } } A.swap(C.A); return (*this); } // A ^= k Matrix pow(long long k) { assert(row() == col()); Matrix B = Matrix::E(row()), X = (*this); while (k) { if (k & 1) B *= X; X *= X; k >>= 1; } A.swap(B.A); return (*this); } Matrix operator+(const Matrix &B) { return ((*this) += B); } Matrix operator-(const Matrix &B) { return ((*this) -= B); } Matrix operator*(const Matrix &B) { return ((*this) *= B); } friend std::ostream &operator<<(std::ostream &os, Matrix &A) { int N = A.row(), M = A.col(); for (int i = 0; i < N; i++) { os << '['; for (int j = 0; j < M; j++) os << A[i][j] << " \n"[j == M - 1]; } return (os); } Matrix &operator+=(const T &k) { int N = row(), M = col(); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) (*this)[i][j] += k; return (*this); } Matrix &operator-=(const T &k) { int N = row(), M = col(); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) (*this)[i][j] -= k; return (*this); } Matrix &operator*=(const T &k) { int N = row(), M = col(); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) (*this)[i][j] *= k; return (*this); } Matrix &operator/=(const T &k) { int N = row(), M = col(); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) (*this)[i][j] /= k; return (*this); } Matrix operator+(const T &k) { return ((*this) += k); } Matrix operator-(const T &k) { return ((*this) -= k); } Matrix operator*(const T &k) { return ((*this) *= k); } Matrix operator/(const T &k) { return ((*this) /= k); } };