Matrix(行列) (structure/matrix.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-12-08 13:43:43+09:00

なにこれ

行列演算のライブラリ．

コンストラクタ

• 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$ 列の行列を扱うとする．

• コンストラクタ：$O(HW)$
• assign()：$O(HW)$
• height(), width()：$O(1)$
• in()：$O(HW)$
• out()：$O(HW)$
• operator[](idx)：$O(1)$
• identiry(n)：$O(n^2)$
• 行列和・行列差：$O(HW)$

$H_1$ 行 $W_1$ 列の行列と $H_2$ 行 $W_2$ 列の行列を扱うとする．

• 行列積：$O(H_1W_1W_2)$

$k$ 次正方行列を扱うとする．

• pow(ex)：$O(k^3 \log \mathrm{ex})$

参考

• 初期化子リスト - cpprefjp C++日本語リファレンス

Verified with

• test/aoj_ITP1_7_D.cpp

Code

#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;
	}
};

Back to top page