This documentation is automatically generated by online-judge-tools/verification-helper
#include "math/semiring_matrix.hpp"
#pragma once
template <class S, S (*add)(S, S), S (*zero)(), S (*mul)(S, S), S (*one)()>
struct Matrix {
std::vector<std::vector<S>> a;
Matrix() {
}
Matrix(size_t n, size_t m) : a(n, std::vector<S>(m, zero())) {
}
Matrix(std::vector<std::vector<S>> _a) {
for (size_t i = 1; i < _a.size(); i++) {
assert(_a[0].size() == _a[i].size());
}
a = std::move(_a);
}
static Matrix e(size_t n) {
Matrix ret(n, n);
for (size_t i = 0; i < n; i++) ret[i][i] = one();
return ret;
}
inline const std::vector<S>& operator[](int i) const {
return a[i];
}
inline std::vector<S>& operator[](int i) {
return a[i];
}
Matrix& operator*=(const Matrix& rhs) {
assert(a[0].size() == rhs.a.size());
std::vector ret(a.size(), std::vector<S>(rhs[0].size(), zero()));
for (size_t i = 0; i < a.size(); i++) {
for (size_t j = 0; j < rhs[0].size(); j++) {
for (size_t k = 0; k < a[0].size(); k++) {
ret[i][j] = add(ret[i][j], mul(a[i][k], rhs[k][j]));
}
}
}
a = std::move(ret);
return *this;
}
Matrix operator*(const Matrix& rhs) const {
return Matrix(*this) *= rhs;
}
Matrix pow(long long k) const {
assert(0 <= k);
Matrix x = *this, ret = Matrix::e(a.size());
while (k > 0) {
if (k & 1) ret *= x;
x *= x;
k >>= 1;
}
return ret;
}
};
#line 2 "math/semiring_matrix.hpp"
template <class S, S (*add)(S, S), S (*zero)(), S (*mul)(S, S), S (*one)()>
struct Matrix {
std::vector<std::vector<S>> a;
Matrix() {
}
Matrix(size_t n, size_t m) : a(n, std::vector<S>(m, zero())) {
}
Matrix(std::vector<std::vector<S>> _a) {
for (size_t i = 1; i < _a.size(); i++) {
assert(_a[0].size() == _a[i].size());
}
a = std::move(_a);
}
static Matrix e(size_t n) {
Matrix ret(n, n);
for (size_t i = 0; i < n; i++) ret[i][i] = one();
return ret;
}
inline const std::vector<S>& operator[](int i) const {
return a[i];
}
inline std::vector<S>& operator[](int i) {
return a[i];
}
Matrix& operator*=(const Matrix& rhs) {
assert(a[0].size() == rhs.a.size());
std::vector ret(a.size(), std::vector<S>(rhs[0].size(), zero()));
for (size_t i = 0; i < a.size(); i++) {
for (size_t j = 0; j < rhs[0].size(); j++) {
for (size_t k = 0; k < a[0].size(); k++) {
ret[i][j] = add(ret[i][j], mul(a[i][k], rhs[k][j]));
}
}
}
a = std::move(ret);
return *this;
}
Matrix operator*(const Matrix& rhs) const {
return Matrix(*this) *= rhs;
}
Matrix pow(long long k) const {
assert(0 <= k);
Matrix x = *this, ret = Matrix::e(a.size());
while (k > 0) {
if (k & 1) ret *= x;
x *= x;
k >>= 1;
}
return ret;
}
};