CompetitivePrograming/Modulo_template.cpp at master · taiseiKMC/CompetitivePrograming · GitHub

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
94
95
96
97
98
99
100
101
using mod_type = long long;
template<mod_type MODULO=1000000007>
class Mod
{
	public:
		using value_type = mod_type;

	private:
		value_type value;
		constexpr value_type Normalize(value_type x) const
		{
			return x<0?(x%MODULO+MODULO):(x%MODULO);
		}

	public:
		constexpr Mod<MODULO>():value(0){}
		constexpr Mod<MODULO>(const value_type &val):value(Normalize(val)) {}

		explicit operator value_type () const
		{
			return value;
		}

		constexpr const Mod<MODULO> operator -() const
		{
			return Mod<MODULO>(MODULO - value);
		}
		constexpr const Mod<MODULO> operator +(const Mod<MODULO> &rhs) const
		{
			return Mod<MODULO>(value + rhs.value);
		}
		constexpr const Mod<MODULO> operator -(const Mod<MODULO> &rhs) const
		{
			return Mod<MODULO>(value + (-rhs).value);
		}
		constexpr const Mod<MODULO> operator *(const Mod<MODULO> &rhs) const
		{
			return Mod<MODULO>(value * rhs.value);
		}
		Mod<MODULO> &operator +=(const Mod<MODULO> &rhs)
		{
			return *this = *this + rhs;
		}
		Mod<MODULO> &operator -=(const Mod<MODULO> &rhs)
		{
			return *this = *this - rhs;
		}
		Mod<MODULO> &operator *=(const Mod<MODULO> &rhs)
		{
			return *this = *this * rhs;
		}


		Mod<MODULO> pow(value_type p) const;

		Mod<MODULO> inv() const
		{
			return pow(MODULO-2);
		}

		const Mod<MODULO> operator /(const Mod<MODULO> &rhs) const
		{
			return *this * rhs.inv();
		}
		Mod<MODULO> &operator /=(const Mod<MODULO> &rhs)
		{
			return *this = *this / rhs;
		}

		constexpr const bool operator <(const Mod<MODULO> &rhs) const
		{
			return value < rhs.value;
		}
		constexpr const bool operator ==(const Mod<MODULO> &rhs) const
		{
			return value == rhs.value;
		}
};

template<mod_type MODULO>
Mod<MODULO> Mod<MODULO>::pow(value_type p) const
{
	Mod<MODULO> tmp=1, mult=*this;
	while(p)
	{
		if((p&1)>0) tmp*=mult;
		p>>=1;
		mult*=mult;
	}
	return tmp;
}

namespace std
{
	template<mod_type MODULO>
	ostream& operator<<(ostream& os, const Mod<MODULO> mod)
	{
		os<<(typename Mod<MODULO>::value_type)mod;
		return os;
	}
};