---
# System prepended metadata

title: matrix calculation
tags: [codebook]

---

---
tags: codebook
---

{%hackmd theme-dark %}

# matrix calculation

## latest

```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#define endl '\n'
using namespace std;
constexpr int mod = 1e9 + 7;
template<int n, int m>
struct matrix {
	vector<vector<int>> data;
	vector<int>& operator[](size_t x) {return data[x];}
	const vector<int>& operator[](size_t x) const {return data[x];}
	matrix(): data(n, vector<int>(m)) {}
	matrix(initializer_list<initializer_list<int>> x): data(n, vector<int>(m)) {
		int tmp = 0;
		for (const auto& i : x)
			data[tmp++].assign(i);
	}
};
template<int n, int m, int k>
matrix<n, m> operator*(const matrix<n, k>& a, const matrix<k, m>& b) {
	matrix<n, m> ret;
	for (int i = 0; i != n; i++)
		for (int j = 0; j != m; j++)
			for (int l = 0; l != k; l++)
				ret[i][j] += 1LL * a[i][l] * b[l][j] % mod, ret[i][j] %= mod;
	return ret;
}
template<int n>
matrix<n, n> unit() {
	matrix<n, n> ret;
	for (int i = 0; i != n; i++)
		ret[i][i] = 1;
	return ret;
}
template<int n>
matrix<n, n> pow(matrix<n, n> a, long long b) {
	matrix<n, n> ret = unit<n>();
	for (; b; b >>= 1, a = a * a)
		if (b & 1) ret = ret * a;
	return ret;
}
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	matrix<3, 3> trans{
		{0, 1, 0},
		{0, 0, 1},
		{1, 1, 1}
	};
	int n;
	while (cin >> n)
		cout << (pow(trans, n - 1) * matrix<3, 1> {{1}, {2}, {4}})[0][0] << endl;
	return 0;
}
```

## old ver

```cpp=
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
constexpr long long mod = 1e9 + 7;
struct matrix {
	vector<vector<long long>> data;
	pair<size_t, size_t> size() const {return {data.size(), data.front().size()};}
	vector<long long>& operator[](const size_t& x) {return data[x];}
	const vector<long long>& operator[] (const size_t& x)const {return data[x];}
	void resize(const size_t& a, const size_t& b, const long long& val = 0) {
		for (auto& i : data) i.resize(b, val);
		data.resize(a, vector<long long>(b, val));
	}
	void assign(const size_t& a, const size_t& b, const long long& val) {
		data.assign(a, vector<long long>(b, val));
	}
	matrix(const vector<vector<long long>>&v = {}): data(v) {}
	matrix(const size_t& a, const size_t& b, const long long& val = 0) {
		assign(a, b, val);
	}
};
matrix operator*(const matrix& a, const matrix& b) {
	matrix tmp(vector<vector<long long>>(a.size().first, vector<long long>(b.size().second, 0)));
	for (size_t i = 0; i != tmp.size().first; i++) {
		for (size_t j = 0; j != tmp.size().second; j++) {
			for (size_t k = 0; k != a.size().second; k++)
				tmp[i][j] += a[i][k] * b[k][j] % mod;
			tmp[i][j] %= mod;
		}
	}
	return tmp;
}
matrix operator+(matrix a, const matrix& b) {
	for (size_t i = 0; i != a.size().first; i++)
		for (size_t j = 0; j != a.size().second; j++)
			a[i][j] -= b[i][j];
	return a;
}
matrix operator-(matrix a) {
	for (auto& i : a.data)
		for (auto& j : i)
			j = -j;
	return a;
}
matrix operator-(matrix a, const matrix& b) {
	return a + (-b);
}
bool operator==(const matrix& a, const matrix& b) {
	if (a.size() != b.size()) return false;
	for (size_t i = 0; i != a.size().first; i++)
		for (size_t j = 0; j != a.size().second; j++)
			if (a[i][j] != b[i][j]) return false;
	return true;
}
bool operator!=(const matrix& a, const matrix& b) {
	return !(a == b);
}
matrix operator*=(matrix& a, const matrix& b) {
	return a = a * b;
}
matrix operator+=(matrix& a, const matrix& b) {
	return a = a + b;
}
matrix operator-=(matrix& a, const matrix& b) {
	return a = a - b;
}
matrix pow(matrix a, unsigned long long b) {
	matrix re(vector<vector<long long>>(a.size().first, vector<long long>(a.size().second, 0)));
	for (size_t i = 0; i < min(a.size().first, a.size().second); i++) re[i][i] = 1;
	for (; b; b >>= 1, a = a * a)
		if (b & 1) re = re * a;
	return re;
}
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	vector<vector<long long>> arr{{1, 1}, {1, 0}};
	unsigned long long n; matrix fib(arr);
	while (cin >> n)
		cout << pow(fib, n + 1)[1][1] << endl;
	return 0;
}
```

## template

```cpp=
template<typename T>
struct matrix {
	vector<vector<T>> data;
	pair<size_t, size_t> size() const {return {data.size(), data.front().size()};}
	vector<T>& operator[](const size_t& x) {return data[x];}
	const vector<T>& operator[] (const size_t& x)const {return data[x];}
	void resize(const size_t& a, const size_t& b, const T& val = 0) {
		for (auto& i : data) i.resize(b, val);
		data.resize(a, vector<T>(b, val));
	}
	void assign(const size_t& a, const size_t& b, const T& val) {
		data.assign(a, vector<T>(b, val));
	}
	matrix(const vector<vector<T>>&v = {}): data(v) {}
	matrix(const size_t& a, const size_t& b, const T& val = 0) {
		assign(a, b, val);
	}
};
template<typename T>
matrix<T> operator*(const matrix<T>& a, const matrix<T>& b) {
	matrix<T> tmp(vector<vector<T>>(a.size().first, vector<T>(b.size().second, 0)));
	for (size_t i = 0; i != tmp.size().first; i++) {
		for (size_t j = 0; j != tmp.size().second; j++) {
			for (size_t k = 0; k != a.size().second; k++)
				tmp[i][j] += a[i][k] * b[k][j];
			tmp[i][j];
		}
	}
	return tmp;
}
template<typename T>
matrix<T> operator+(matrix<T> a, const matrix<T>& b) {
	for (size_t i = 0; i != a.size().first; i++)
		for (size_t j = 0; j != a.size().second; j++)
			a[i][j] -= b[i][j];
	return a;
}
template<typename T>
matrix<T> operator-(matrix<T> a) {
	for (auto& i : a.data)
		for (auto& j : i)
			j = -j;
	return a;
}
template<typename T>
matrix<T> operator-(matrix<T> a, const matrix<T>& b) {
	return a + (-b);
}
template<typename T>
bool operator==(const matrix<T>& a, const matrix<T>& b) {
	if (a.size() != b.size()) return false;
	for (size_t i = 0; i != a.size().first; i++)
		for (size_t j = 0; j != a.size().second; j++)
			if (a[i][j] != b[i][j]) return false;
	return true;
}
template<typename T>
bool operator!=(const matrix<T>& a, const matrix<T>& b) {
	return !(a == b);
}
template<typename T>
matrix<T> operator*=(matrix<T>& a, const matrix<T>& b) {
	return a = a * b;
}
template<typename T>
matrix<T> operator+=(matrix<T>& a, const matrix<T>& b) {
	return a = a + b;
}
template<typename T>
matrix<T> operator-=(matrix<T>& a, const matrix<T>& b) {
	return a = a - b;
}
template<typename T>
matrix<T> pow(matrix<T> a, unsigned long long b) {
	matrix<T> re(vector<vector<T>>(a.size().first, vector<T>(a.size().second, 0)));
	for (size_t i = 0; i < min(a.size().first, a.size().second); i++) re[i][i] = 1;
	for (; b; b >>= 1, a = a * a)
		if (b & 1) re = re * a;
	return re;
}
```