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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221 | #pragma once
#include <concepts><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <type_traits><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include "snippet/aliases.hpp"
#include "internal/concepts.hpp"
#include "numeric/modular/builtin_reduction.hpp"
#include "numeric/modular/binary_reduction.hpp"
#include "numeric/modular/barrett_reduction.hpp"
#include "numeric/modular/montgomery_reduction.hpp"
namespace uni {
namespace internal {
template<class T>
concept modint_family =
numeric<T> &&
has_static_one<T> && has_static_zero<T> &&
requires (T v, i64 p, typename T::value_type x) {
{ v.pow(p) } -> std::same_as<T>;
{ v.inv() } -> std::same_as<T>;
{ T::raw(x) } -> std::same_as<T>;
{ v.val() } -> std::same_as<typename T::value_type>;
{ T::mod() } -> std::same_as<typename T::value_type>;
{ T::max() } -> std::same_as<typename T::value_type>;
T::digits;
T::context::dynamic;
};
template<class T>
concept dynamic_modint_family =
modint_family<T> &&
T::context::dynamic &&
requires (typename T::value_type v) {
T::set_mod(v);
};
template<class T>
concept static_modint_family =
modint_family<T> &&
(!T::context::dynamic); //&&
// requires {
// T::is_prime;
// };
template<class T>
concept modular_reduction =
std::default_initializable<T> &&
std::constructible_from<T, typename T::value_type> &&
requires (T v, typename T::value_type x, i64 p) {
typename T::value_type;
T::digits;
{ T::max() } -> std::same_as<typename T::value_type>;
{ v.mod() } -> std::same_as<typename T::value_type>;
{ v.reduce(x) } -> std::same_as<typename T::value_type>;
{ v.add(x, x) } -> std::same_as<typename T::value_type>;
{ v.subtract(x, x) } -> std::same_as<typename T::value_type>;
{ v.multiply(x, x) } -> std::same_as<typename T::value_type>;
{ v.multiply(x, x) } -> std::same_as<typename T::value_type>;
{ v.pow(x, p) } -> std::same_as<typename T::value_type>;
{ v.convert_raw(x) } -> std::same_as<typename T::value_type>;
{ v.convert(x) } -> std::same_as<typename T::value_type>;
{ v.revert(x) } -> std::same_as<typename T::value_type>;
v.compare(x, x);
};
template<class T>
concept modular_context =
requires {
typename T::reductor;
typename T::value_type;
T::reduction;
};
} // namespace internal
template<internal::modular_reduction Reduction, typename Reduction::value_type Mod>
struct static_modular_context {
using reductor = Reduction;
using value_type = typename reductor::value_type;
static constexpr bool dynamic = false;
static constexpr reductor reduction = reductor(Mod);
private:
using context = static_modular_context;
};
template<internal::modular_reduction Reduction, i64 Id>
struct dynamic_modular_context {
using reductor = Reduction;
using value_type = typename reductor::value_type;
static constexpr bool dynamic = true;
static inline reductor reduction;
private:
using context = dynamic_modular_context;
public:
static constexpr void set_mod(const value_type mod) noexcept(NO_EXCEPT) { context::reduction = reductor(mod); }
};
template<internal::modular_context> struct modint;
template<u32 Mod> using static_builtin_modular_context_32bit = static_modular_context<builtin_reduction_32bit, Mod>;
template<u64 Mod> using static_builtin_modular_context_64bit = static_modular_context<builtin_reduction_64bit, Mod>;
template<u32 Mod> using static_barrett_modular_context_32bit = static_modular_context<barrett_reduction_32bit, Mod>;
template<u64 Mod> using static_barrett_modular_context_64bit = static_modular_context<barrett_reduction_64bit, Mod>;
template<u32 Mod> using static_montgomery_modular_context_32bit = static_modular_context<montgomery_reduction_32bit, Mod>;
template<u64 Mod> using static_montgomery_modular_context_64bit = static_modular_context<montgomery_reduction_64bit, Mod>;
template<u32 Mod> using static_arbitrary_montgomery_modular_context_32bit = static_modular_context<arbitrary_montgomery_reduction_32bit, Mod>;
template<u64 Mod> using static_arbitrary_montgomery_modular_context_64bit = static_modular_context<arbitrary_montgomery_reduction_64bit, Mod>;
template<u32 Mod> using static_binary_modular_context_32bit = static_modular_context<binary_reduction_32bit, Mod>;
template<u64 Mod> using static_binary_modular_context_64bit = static_modular_context<binary_reduction_64bit, Mod>;
template<u128 Mod> using static_binary_modular_context_128bit = static_modular_context<binary_reduction_128bit, Mod>;
template<u32 Mod> using static_builtin_modint_32bit = modint<static_builtin_modular_context_32bit<Mod>>;
template<u64 Mod> using static_builtin_modint_64bit = modint<static_builtin_modular_context_64bit<Mod>>;
template<u32 Mod> using static_barrett_modint_32bit = modint<static_barrett_modular_context_32bit<Mod>>;
template<u64 Mod> using static_barrett_modint_64bit = modint<static_barrett_modular_context_64bit<Mod>>;
template<u32 Mod> using static_montgomery_modint_32bit = modint<static_montgomery_modular_context_32bit<Mod>>;
template<u64 Mod> using static_montgomery_modint_64bit = modint<static_montgomery_modular_context_64bit<Mod>>;
template<u32 Mod> using static_arbitrary_montgomery_modint_32bit = modint<static_arbitrary_montgomery_modular_context_32bit<Mod>>;
template<u64 Mod> using static_arbitrary_montgomery_modint_64bit = modint<static_arbitrary_montgomery_modular_context_64bit<Mod>>;
template<u32 Mod> using static_binary_modint_32bit = modint<static_binary_modular_context_32bit<Mod>>;
template<u64 Mod> using static_binary_modint_64bit = modint<static_binary_modular_context_64bit<Mod>>;
template<u128 Mod> using static_binary_modint_128bit = modint<static_binary_modular_context_128bit<Mod>>;
template<i64 Id> using dynamic_builtin_modular_context_32bit = dynamic_modular_context<builtin_reduction_32bit, Id>;
template<i64 Id> using dynamic_builtin_modular_context_64bit = dynamic_modular_context<builtin_reduction_64bit, Id>;
template<i64 Id> using dynamic_barrett_modular_context_32bit = dynamic_modular_context<barrett_reduction_32bit, Id>;
template<i64 Id> using dynamic_barrett_modular_context_64bit = dynamic_modular_context<barrett_reduction_64bit, Id>;
template<i64 Id> using dynamic_montgomery_modular_context_32bit = dynamic_modular_context<montgomery_reduction_32bit, Id>;
template<i64 Id> using dynamic_montgomery_modular_context_64bit = dynamic_modular_context<montgomery_reduction_64bit, Id>;
template<i64 Id> using dynamic_arbitrary_montgomery_modular_context_32bit = dynamic_modular_context<arbitrary_montgomery_reduction_32bit, Id>;
template<i64 Id> using dynamic_arbitrary_montgomery_modular_context_64bit = dynamic_modular_context<arbitrary_montgomery_reduction_64bit, Id>;
template<i64 Id> using dynamic_binary_modular_context_32bit = dynamic_modular_context<binary_reduction_32bit, Id>;
template<i64 Id> using dynamic_binary_modular_context_64bit = dynamic_modular_context<binary_reduction_64bit, Id>;
template<i64 Id> using dynamic_binary_modular_context_128bit = dynamic_modular_context<binary_reduction_128bit, Id>;
template<i64 Id> using dynamic_builtin_modint_32bit = modint<dynamic_builtin_modular_context_32bit<Id>>;
template<i64 Id> using dynamic_builtin_modint_64bit = modint<dynamic_builtin_modular_context_64bit<Id>>;
template<i64 Id> using dynamic_barrett_modint_32bit = modint<dynamic_barrett_modular_context_32bit<Id>>;
template<i64 Id> using dynamic_barrett_modint_64bit = modint<dynamic_barrett_modular_context_64bit<Id>>;
template<i64 Id> using dynamic_montgomery_modint_32bit = modint<dynamic_montgomery_modular_context_32bit<Id>>;
template<i64 Id> using dynamic_montgomery_modint_64bit = modint<dynamic_montgomery_modular_context_64bit<Id>>;
template<i64 Id> using dynamic_arbitrary_montgomery_modint_32bit = modint<dynamic_arbitrary_montgomery_modular_context_32bit<Id>>;
template<i64 Id> using dynamic_arbitrary_montgomery_modint_64bit = modint<dynamic_arbitrary_montgomery_modular_context_64bit<Id>>;
template<i64 Id> using dynamic_binary_modint_32bit = modint<dynamic_binary_modular_context_32bit<Id>>;
template<i64 Id> using dynamic_binary_modint_64bit = modint<dynamic_binary_modular_context_64bit<Id>>;
template<i64 Id> using dynamic_binary_modint_128bit = modint<dynamic_binary_modular_context_128bit<Id>>;
template<u32 Mod> using static_modint_32bit = static_builtin_modint_32bit<Mod>;
template<u64 Mod> using static_modint_64bit = static_builtin_modint_64bit<Mod>;
using modint998244353 = static_modint_32bit<998244353>;
using modint1000000007 = static_modint_32bit<1000000007>;
using modint_32 = dynamic_barrett_modint_32bit<-1>;
using modint_64 = dynamic_barrett_modint_64bit<-1>;
template<const unsigned Val, const unsigned Mod = 998244353>
const uni::static_modint_32bit<Mod> MINT = Val;
template<const unsigned Val, const unsigned Mod = 998244353>
const unsigned INV = uni::static_modint_32bit<Mod>{ Val }.inv().val();
template<const unsigned Val, const unsigned Mod = 998244353>
const int SINV = uni::static_modint_32bit<Mod>{ Val }.inv().val();
} // namespace uni
|