---
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;
}
```
Sign in with Wallet
Connect another wallet