This documentation is automatically generated by competitive-verifier/competitive-verifier
行列演算のライブラリ.
matrix()
:$0$ 行 $0$ 列の行列を作る.matrix(h, w)
:h
行 w
列の行列を作る.matrix(h, w, init)
:init
を初期値とする h
行 w
列の行列を作る.matrix(m_init)
:m_init
を初期値とする行列を作る.assign(h, w)
:h
行 w
列の行列を作る.assign(h, w, init)
:init
を初期値とする h
行 w
列の行列を作る.height()
, width()
:行列の縦・横のサイズを返す.in()
:現在の要素サイズ分だけ標準入力する.in(h, w)
:h
行 w
列の行列を作り標準入力する.out()
:要素を空白区切りで標準出力する.operator[](idx)
:idx
番目の要素である $1$ 次元配列の参照を返す.vector
を用いた多次元配列と同様に扱える.operator+, operator-, operator*
:行列和・行列差・行列積.通常の算術演算子と同様に扱える.pow(ex)
:行列累乗の結果を返す.
static identity(n)
:n
次単位行列を返す.$H$ 行 $W$ 列の行列を扱うとする.
assign()
:$O(HW)$height()
, width()
:$O(1)$in()
:$O(HW)$out()
:$O(HW)$operator[](idx)
:$O(1)$identiry(n)
:$O(n^2)$$H_1$ 行 $W_1$ 列の行列と $H_2$ 行 $W_2$ 列の行列を扱うとする.
$k$ 次正方行列を扱うとする.
pow(ex)
:$O(k^3 \log \mathrm{ex})$#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> struct matrix {
private:
vector<vector<T>> m;
public:
matrix() {}
matrix(int h, int w) : m(h, vector<T>(w)) {}
matrix(int h, int w, T init) : m(h, vector<T>(w, init)) {}
matrix(const initializer_list<initializer_list<T>> m_init) : m(m_init.begin(), m_init.end()) {}
void assign(int h, int w) {
m.assign(h, vector<T>(w));
}
void assign(int h, int w, const T init) {
m.assign(h, vector<T>(w, init));
}
int height() const {
return m.size();
}
int width() const {
if(height() == 0) return 0;
return m[0].size();
}
void in() {
for(vector<T> &v : m)
for(T &val : v) cin >> val;
}
void in(int h, int w) {
m.resize(h, vector<T>(w));
in();
}
void out() {
int w = width();
for(vector<T> &v : m)
for(int j = 0; j < w; j++) {
cout << v[j] << (j == w - 1 ? '\n' : ' ');
}
cout << flush;
}
inline const vector<T> &operator[](int idx) const {
assert(0 <= idx && idx < m.size());
return m[idx];
}
inline vector<T> &operator[](int idx) {
assert(0 <= idx && idx < m.size());
return m[idx];
}
matrix &operator+=(const matrix &a) {
int h = height(), w = width();
assert(h == a.height() && w == a.width());
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++) m[i][j] += a[i][j];
return *this;
}
matrix &operator-=(const matrix &a) {
int h = height(), w = width();
assert(h == a.height() && w == a.width());
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++) m[i][j] -= a[i][j];
return *this;
}
matrix &operator*=(const matrix &a) {
int h = height(), w = a.width(), ah = a.height();
assert(width() == ah);
vector<vector<T>> tmp(h, vector(w, T(0)));
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++)
for(int k = 0; k < ah; k++) tmp[i][j] += m[i][k] * a[k][j];
m.swap(tmp);
return *this;
}
matrix operator+(const matrix &a) const {
return matrix(*this) += a;
}
matrix operator-(const matrix &a) const {
return matrix(*this) -= a;
}
matrix operator*(const matrix &a) const {
return matrix(*this) *= a;
}
matrix pow(long long ex) {
matrix a = this->m;
matrix res = identity(a.height());
while(ex > 0) {
if(ex & 1) res *= a;
ex >>= 1;
a *= a;
}
return res;
}
static matrix identity(int n) {
matrix res(n, n, 0);
for(int i = 0; i < n; i++) res[i][i] = 1;
return res;
}
};
#line 2 "structure/matrix.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> struct matrix {
private:
vector<vector<T>> m;
public:
matrix() {}
matrix(int h, int w) : m(h, vector<T>(w)) {}
matrix(int h, int w, T init) : m(h, vector<T>(w, init)) {}
matrix(const initializer_list<initializer_list<T>> m_init) : m(m_init.begin(), m_init.end()) {}
void assign(int h, int w) {
m.assign(h, vector<T>(w));
}
void assign(int h, int w, const T init) {
m.assign(h, vector<T>(w, init));
}
int height() const {
return m.size();
}
int width() const {
if(height() == 0) return 0;
return m[0].size();
}
void in() {
for(vector<T> &v : m)
for(T &val : v) cin >> val;
}
void in(int h, int w) {
m.resize(h, vector<T>(w));
in();
}
void out() {
int w = width();
for(vector<T> &v : m)
for(int j = 0; j < w; j++) {
cout << v[j] << (j == w - 1 ? '\n' : ' ');
}
cout << flush;
}
inline const vector<T> &operator[](int idx) const {
assert(0 <= idx && idx < m.size());
return m[idx];
}
inline vector<T> &operator[](int idx) {
assert(0 <= idx && idx < m.size());
return m[idx];
}
matrix &operator+=(const matrix &a) {
int h = height(), w = width();
assert(h == a.height() && w == a.width());
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++) m[i][j] += a[i][j];
return *this;
}
matrix &operator-=(const matrix &a) {
int h = height(), w = width();
assert(h == a.height() && w == a.width());
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++) m[i][j] -= a[i][j];
return *this;
}
matrix &operator*=(const matrix &a) {
int h = height(), w = a.width(), ah = a.height();
assert(width() == ah);
vector<vector<T>> tmp(h, vector(w, T(0)));
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++)
for(int k = 0; k < ah; k++) tmp[i][j] += m[i][k] * a[k][j];
m.swap(tmp);
return *this;
}
matrix operator+(const matrix &a) const {
return matrix(*this) += a;
}
matrix operator-(const matrix &a) const {
return matrix(*this) -= a;
}
matrix operator*(const matrix &a) const {
return matrix(*this) *= a;
}
matrix pow(long long ex) {
matrix a = this->m;
matrix res = identity(a.height());
while(ex > 0) {
if(ex & 1) res *= a;
ex >>= 1;
a *= a;
}
return res;
}
static matrix identity(int n) {
matrix res(n, n, 0);
for(int i = 0; i < n; i++) res[i][i] = 1;
return res;
}
};