/
semiring.hpp
93 lines (80 loc) · 2.42 KB
/
semiring.hpp
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#pragma once
template <typename T, T (*add)(T, T), T (*mul)(T, T), T (*I0)(), T (*I1)()>
struct semiring {
T x;
semiring() : x(I0()) {}
semiring(T y) : x(y) {}
static T id0() { return I0(); }
static T id1() { return I1(); }
semiring &operator+=(const semiring &p) {
if (x == I0()) return *this = p;
if (p.x == I0()) return *this;
return *this = add(x, p.x);
}
semiring &operator*=(const semiring &p) {
if (x == I0() || p.x == I0()) return *this = I0();
if (x == I1()) return *this = p;
if (p.x == I1()) return *this;
return *this = mul(x, p.x);
}
semiring operator+(const semiring &p) const { return semiring(*this) += p; }
semiring operator*(const semiring &p) const { return semiring(*this) *= p; }
bool operator==(const semiring &p) const { return x == p.x; }
bool operator!=(const semiring &p) const { return x != p.x; }
friend ostream &operator<<(ostream &os, const semiring &p) {
return os << p.x;
}
};
template <typename rig, int N>
struct Mat {
using Array = array<array<rig, N>, N>;
Array A;
Mat() {
for (int i = 0; i < N; i++) A[i].fill(rig::id0());
}
int height() const { return N; }
int width() const { return N; }
inline const array<rig, N> &operator[](int k) const { return A[k]; }
inline array<rig, N> &operator[](int k) { return A[k]; }
static Mat I() {
Mat m;
for (int i = 0; i < N; i++) m[i][i] = rig::id1();
return m;
}
Mat &operator+=(const Mat &B) {
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) A[i][j] += B[i][j];
return (*this);
}
Mat &operator*=(const Mat &B) {
Mat C;
for (int i = 0; i < N; i++)
for (int k = 0; k < N; k++)
for (int j = 0; j < N; j++) C[i][j] += A[i][k] * B[k][j];
A.swap(C.A);
return (*this);
}
Mat &operator^=(long long k) {
Mat B = Mat::I();
for (; k; *this *= *this, k >>= 1)
if (k & 1) B *= *this;
A.swap(B.A);
return (*this);
}
Mat operator+(const Mat &B) const { return (Mat(*this) += B); }
Mat operator*(const Mat &B) const { return (Mat(*this) *= B); }
Mat operator^(long long k) const { return (Mat(*this) ^= k); }
friend ostream &operator<<(ostream &os, Mat &p) {
for (int i = 0; i < N; i++) {
os << "[";
for (int j = 0; j < N; j++) {
os << p[i][j].x << (j == N - 1 ? "]\n" : ",");
}
}
return (os);
}
};
/**
* @brief 半環ライブラリ
* @docs docs/math/semiring.md
*/