1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| template<typename T>
class Matrix
{
private:
vector<vector<T>> a; int n, m; T mod = 0;
public:
Matrix(int h, int w) {n = h; m = w; a.resize(n + 1, vector<T>(m + 1));}
Matrix(const Matrix &b) {n = b.n; m = b.m; a = b.a; mod = b.mod;}
explicit Matrix(const vector<vector<T>> &b)
{
n = b.size();
m = b[0].size();
a.resize(n + 1, vector<T>(m + 1));
rep(i, 1, n) rep(j, 1, m) a[i][j] = b[i - 1][j - 1];
}
Matrix &operator=(const Matrix &b) {a = b.a; return *this;}
T &operator()(int i, int j) {return a[i][j];}
Matrix operator+(const Matrix &b) const
{
Matrix<T> res(n, m); res.setmod(mod);
rep(i, 1, n) rep(j, 1, m)
if (mod) res.a[i][j] = (a[i][j] + b.a[i][j]) % mod;
else res.a[i][j] = a[i][j] + b.a[i][j];
return res;
}
Matrix operator+=(const Matrix &b) {return *this = *this + b;}
Matrix operator*(const Matrix &b) const
{
if (m != b.n) return Matrix(0, 0);
Matrix<T> res(n, b.m); res.setmod(mod);
rep(i, 1, n) rep(j, 1, b.m) rep(l, 1, m)
if (mod) (res.a[i][j] += a[i][l] * b.a[l][j] % mod) %= mod;
else res.a[i][j] += a[i][l] * b.a[l][j];
return res;
}
Matrix operator*=(const Matrix &b) {return *this = *this * b;}
Matrix operator^(T b) const
{
if (n != m) return Matrix(0, 0);
Matrix<T> res(n, n), a(*this); res.setmod(mod);
rep(i, 1, n) rep(j, 1, n) res.a[i][j] = i == j;
for (; b; b >>= 1, a *= a) if (b & 1) res *= a;
return res;
}
Matrix operator^=(T b) {return *this = *this ^ b;}
void print() const
{
rep(i, 1, n)
{
rep(j, 1, m) cout << a[i][j] << ' ';
cout << '\n';
}
}
void input()
{
rep(i, 1, n) rep(j, 1, m) cin >> a[i][j];
}
void setmod(int x) {mod = x;}
};
|