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
| template <typename T>
T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) res *= a;
}
return res;
}
template <int P>
struct MintBase {
int v;
int norm(int x) const {
if (x >= P) x -= P;
if (x < 0) x += P;
return x;
}
MintBase() : v{0} {}
MintBase(i64 x) : v{norm(x % P)} {}
int val() const { return v; }
MintBase operator-() const { return MintBase(norm(P - v)); }
MintBase inv() const {
assert(v != 0);
return power(*this, P - 2);
}
MintBase &operator+=(const MintBase &rhs) {
v = norm(v + rhs.v);
return *this;
}
MintBase &operator-=(const MintBase &rhs) {
v = norm(v - rhs.v);
return *this;
}
MintBase &operator*=(const MintBase &rhs) {
v = norm(1LL * v * rhs.v % P);
return *this;
}
MintBase &operator/=(const MintBase &rhs) {
return *this *= rhs.inv();
}
friend MintBase operator+(const MintBase &lhs, const MintBase &rhs) {
MintBase res = lhs;
res += rhs;
return res;
}
friend MintBase operator-(const MintBase &lhs, const MintBase &rhs) {
MintBase res = lhs;
res -= rhs;
return res;
}
friend MintBase operator*(const MintBase &lhs, const MintBase &rhs) {
MintBase res = lhs;
res *= rhs;
return res;
}
friend MintBase operator/(const MintBase &lhs, const MintBase &rhs) {
MintBase res = lhs;
res /= rhs;
return res;
}
friend std::istream &operator>>(std::istream &is, MintBase &a) {
i64 x;
is >> x;
a = MintBase(x);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const MintBase &a) {
return os << a.val();
}
friend bool operator==(const MintBase &lhs, const MintBase &rhs) {
return lhs.val() == rhs.val();
}
};
|
