Felix's Library
This documentation is automatically generated by online-judge-tools/verification-helper
library/modint/modint.hpp
- View this file on GitHub
- Last update: 2023-07-31 16:36:45+08:00
- Include:
#include "library/modint/modint.hpp" - Link: View error logs on GitHub Actions
Depends on
Required by
Verified with
test/convolution/ntt/yosupo-Convolution-Large.test.cpp
- test/convolution/ntt/yosupo-Convolution-Mod-1000000007.test.cpp
- test/convolution/ntt/yosupo-Convolution.test.cpp
- test/convolution/subset-convolution/yosupo-Bitwise-And-Convolution.test.cpp
- test/convolution/subset-convolution/yosupo-Bitwise-Xor-Convolution.test.cpp
- test/convolution/subset-convolution/yosupo-Subset-Convolution.test.cpp
- test/data-structure/lazy-lct/yosupo-Dynamic-Tree-Vertex-Set-Path-Composite.test.cpp
- test/data-structure/lazy-segtree/yosupo-Range-Affine-Point-Get.test.cpp
- test/data-structure/lazy-segtree/yosupo-Range-Affine-Range-Sum.test.cpp
test/data-structure/treap/yosupo-Dynamic-Sequence-Range-Affine-Range-Sum.test.cpp
- test/formal-power-series/poly/yosupo-Exp-of-Formal-Power-Series.test.cpp
- test/formal-power-series/poly/yosupo-Inv-of-Formal-Power-Series.test.cpp
- test/formal-power-series/poly/yosupo-Log-of-Formal-Power-Series.test.cpp
- test/formal-power-series/poly/yosupo-Multipoint-Evaluation.test.cpp
- test/formal-power-series/poly/yosupo-Polynomial-Taylor-Shift.test.cpp
- test/formal-power-series/poly/yosupo-Pow-of-Formal-Power-Series.test.cpp
- test/formal-power-series/poly/yosupo-Product-of-Polynomial-Sequence.test.cpp
- test/formal-power-series/poly/yosupo-Sqrt-of-Formal-Power-Series.test.cpp
- test/formal-power-series/series/yosupo-Partition-Function.test.cpp
- test/matrix/matrix/yosupo-Determinant-of-Matrix.test.cpp
- test/matrix/matrix/yosupo-Matrix-Product.test.cpp
- test/modint/modint/aoj-ntl-Power.test.cpp
- test/modint/modint/yosupo-Sqrt-Mod.test.cpp
- test/tree/hld/yosupo-Vertex-Set-Path-Composite.test.cpp
Code
#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <type_traits>
#include "../misc/type-traits.hpp"
#include "../math/inv-gcd.hpp"
namespace felix {
template<int id>
struct modint {
public:
static constexpr int mod() { return (id > 0 ? id : md); }
static constexpr void set_mod(int m) {
if(id > 0 || md == m) {
return;
}
md = m;
fact.resize(1);
inv_fact.resize(1);
invs.resize(1);
}
static constexpr void prepare(int n) {
int sz = (int) fact.size();
if(sz == mod()) {
return;
}
n = 1 << std::__lg(2 * n - 1);
if(n < sz) {
return;
}
if(n < (sz - 1) * 2) {
n = std::min((sz - 1) * 2, mod() - 1);
}
fact.resize(n + 1);
inv_fact.resize(n + 1);
invs.resize(n + 1);
for(int i = sz; i <= n; i++) {
fact[i] = fact[i - 1] * i;
}
auto eg = internal::inv_gcd(fact.back().val(), mod());
assert(eg.first == 1);
inv_fact[n] = eg.second;
for(int i = n - 1; i >= sz; i--) {
inv_fact[i] = inv_fact[i + 1] * (i + 1);
}
for(int i = n; i >= sz; i--) {
invs[i] = inv_fact[i] * fact[i - 1];
}
}
constexpr modint() : v(0) {}
template<class T, internal::is_signed_int_t<T>* = nullptr> constexpr modint(T x) : v(x >= 0 ? x % mod() : x % mod() + mod()) {}
template<class T, internal::is_unsigned_int_t<T>* = nullptr> constexpr modint(T x) : v(x % mod()) {}
constexpr int val() const { return v; }
constexpr modint inv() const {
if(id > 0 && v < std::min(mod() >> 1, 1 << 18)) {
prepare(v);
return invs[v];
} else {
auto eg = internal::inv_gcd(v, mod());
assert(eg.first == 1);
return eg.second;
}
}
constexpr modint& operator+=(const modint& rhs) & {
v += rhs.v;
if(v >= mod()) {
v -= mod();
}
return *this;
}
constexpr modint& operator-=(const modint& rhs) & {
v -= rhs.v;
if(v < 0) {
v += mod();
}
return *this;
}
constexpr modint& operator*=(const modint& rhs) & {
v = 1LL * v * rhs.v % mod();
return *this;
}
constexpr modint& operator/=(const modint& rhs) & {
return *this *= rhs.inv();
}
friend constexpr modint operator+(modint lhs, modint rhs) { return lhs += rhs; }
friend constexpr modint operator-(modint lhs, modint rhs) { return lhs -= rhs; }
friend constexpr modint operator*(modint lhs, modint rhs) { return lhs *= rhs; }
friend constexpr modint operator/(modint lhs, modint rhs) { return lhs /= rhs; }
constexpr modint operator+() const { return *this; }
constexpr modint operator-() const { return modint() - *this; }
constexpr bool operator==(const modint& rhs) const { return v == rhs.v; }
constexpr bool operator!=(const modint& rhs) const { return v != rhs.v; }
constexpr modint pow(long long p) const {
modint a(*this), res(1);
if(p < 0) {
a = a.inv();
p = -p;
}
while(p) {
if(p & 1) {
res *= a;
}
a *= a;
p >>= 1;
}
return res;
}
constexpr bool has_sqrt() const {
if(mod() == 2 || v == 0) {
return true;
}
if(pow((mod() - 1) / 2).val() != 1) {
return false;
}
return true;
}
constexpr modint sqrt() const {
if(mod() == 2 || v < 2) {
return *this;
}
assert(pow((mod() - 1) / 2).val() == 1);
modint b = 1;
while(b.pow((mod() - 1) >> 1).val() == 1) {
b += 1;
}
int m = mod() - 1, e = __builtin_ctz(m);
m >>= e;
modint x = modint(*this).pow((m - 1) >> 1);
modint y = modint(*this) * x * x;
x *= v;
modint z = b.pow(m);
while(y.val() != 1) {
int j = 0;
modint t = y;
while(t.val() != 1) {
t *= t;
j++;
}
z = z.pow(1LL << (e - j - 1));
x *= z, z *= z, y *= z;
e = j;
}
return x;
}
friend std::istream& operator>>(std::istream& in, modint& num) {
long long x;
in >> x;
num = modint<id>(x);
return in;
}
friend std::ostream& operator<<(std::ostream& out, const modint& num) {
return out << num.val();
}
public:
static std::vector<modint> fact, inv_fact, invs;
private:
int v;
static int md;
};
template<int id> int modint<id>::md = 998244353;
template<int id> std::vector<modint<id>> modint<id>::fact = {1};
template<int id> std::vector<modint<id>> modint<id>::inv_fact = {1};
template<int id> std::vector<modint<id>> modint<id>::invs = {0};
using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1000000007>;
namespace internal {
template<class T> struct is_modint : public std::false_type {};
template<int id> struct is_modint<modint<id>> : public std::true_type {};
template<class T, class ENABLE = void> struct is_static_modint : public std::false_type {};
template<int id> struct is_static_modint<modint<id>, std::enable_if_t<(id > 0)>> : public std::true_type {};
template<class T> using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template<class T, class ENABLE = void> struct is_dynamic_modint : public std::false_type {};
template<int id> struct is_dynamic_modint<modint<id>, std::enable_if_t<(id <= 0)>> : public std::true_type {};
template<class T> using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace felix#line 2 "library/modint/modint.hpp"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <type_traits>
#line 3 "library/misc/type-traits.hpp"
#include <numeric>
#line 5 "library/misc/type-traits.hpp"
namespace felix {
namespace internal {
#ifndef _MSC_VER
template<class T> using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value || std::is_same<T, __int128>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int128 = typename std::conditional<std::is_same<T, __uint128_t>::value || std::is_same<T, unsigned __int128>::value, std::true_type, std::false_type>::type;
template<class T> using make_unsigned_int128 = typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;
template<class T> using is_integral = typename std::conditional<std::is_integral<T>::value || is_signed_int128<T>::value || is_unsigned_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_signed_int = typename std::conditional<(is_integral<T>::value && std::is_signed<T>::value) || is_signed_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int = typename std::conditional<(is_integral<T>::value && std::is_unsigned<T>::value) || is_unsigned_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using to_unsigned = typename std::conditional<is_signed_int128<T>::value, make_unsigned_int128<T>, typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>, std::common_type<T>>::type>::type;
#else
template<class T> using is_integral = typename std::is_integral<T>;
template<class T> using is_signed_int = typename std::conditional<is_integral<T>::value && std::is_signed<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int = typename std::conditional<is_integral<T>::value && std::is_unsigned<T>::value, std::true_type, std::false_type>::type;
template<class T> using to_unsigned = typename std::conditional<is_signed_int<T>::value, std::make_unsigned<T>, std::common_type<T>>::type;
#endif
template<class T> using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template<class T> using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template<class T> using to_unsigned_t = typename to_unsigned<T>::type;
template<class T> struct safely_multipliable {};
template<> struct safely_multipliable<short> { using type = int; };
template<> struct safely_multipliable<unsigned short> { using type = unsigned int; };
template<> struct safely_multipliable<int> { using type = long long; };
template<> struct safely_multipliable<unsigned int> { using type = unsigned long long; };
template<> struct safely_multipliable<long long> { using type = __int128; };
template<> struct safely_multipliable<unsigned long long> { using type = __uint128_t; };
template<class T> using safely_multipliable_t = typename safely_multipliable<T>::type;
} // namespace internal
} // namespace felix
#line 2 "library/math/safe-mod.hpp"
namespace felix {
namespace internal {
template<class T>
constexpr T safe_mod(T x, T m) {
x %= m;
if(x < 0) {
x += m;
}
return x;
}
} // namespace internal
} // namespace felix
#line 3 "library/math/inv-gcd.hpp"
namespace felix {
namespace internal {
template<class T>
constexpr std::pair<T, T> inv_gcd(T a, T b) {
a = safe_mod(a, b);
if(a == 0) {
return {b, 0};
}
T s = b, t = a;
T m0 = 0, m1 = 1;
while(t) {
T u = s / t;
s -= t * u;
m0 -= m1 * u;
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if(m0 < 0) {
m0 += b / s;
}
return {s, m0};
}
} // namespace internal
} // namespace felix
#line 9 "library/modint/modint.hpp"
namespace felix {
template<int id>
struct modint {
public:
static constexpr int mod() { return (id > 0 ? id : md); }
static constexpr void set_mod(int m) {
if(id > 0 || md == m) {
return;
}
md = m;
fact.resize(1);
inv_fact.resize(1);
invs.resize(1);
}
static constexpr void prepare(int n) {
int sz = (int) fact.size();
if(sz == mod()) {
return;
}
n = 1 << std::__lg(2 * n - 1);
if(n < sz) {
return;
}
if(n < (sz - 1) * 2) {
n = std::min((sz - 1) * 2, mod() - 1);
}
fact.resize(n + 1);
inv_fact.resize(n + 1);
invs.resize(n + 1);
for(int i = sz; i <= n; i++) {
fact[i] = fact[i - 1] * i;
}
auto eg = internal::inv_gcd(fact.back().val(), mod());
assert(eg.first == 1);
inv_fact[n] = eg.second;
for(int i = n - 1; i >= sz; i--) {
inv_fact[i] = inv_fact[i + 1] * (i + 1);
}
for(int i = n; i >= sz; i--) {
invs[i] = inv_fact[i] * fact[i - 1];
}
}
constexpr modint() : v(0) {}
template<class T, internal::is_signed_int_t<T>* = nullptr> constexpr modint(T x) : v(x >= 0 ? x % mod() : x % mod() + mod()) {}
template<class T, internal::is_unsigned_int_t<T>* = nullptr> constexpr modint(T x) : v(x % mod()) {}
constexpr int val() const { return v; }
constexpr modint inv() const {
if(id > 0 && v < std::min(mod() >> 1, 1 << 18)) {
prepare(v);
return invs[v];
} else {
auto eg = internal::inv_gcd(v, mod());
assert(eg.first == 1);
return eg.second;
}
}
constexpr modint& operator+=(const modint& rhs) & {
v += rhs.v;
if(v >= mod()) {
v -= mod();
}
return *this;
}
constexpr modint& operator-=(const modint& rhs) & {
v -= rhs.v;
if(v < 0) {
v += mod();
}
return *this;
}
constexpr modint& operator*=(const modint& rhs) & {
v = 1LL * v * rhs.v % mod();
return *this;
}
constexpr modint& operator/=(const modint& rhs) & {
return *this *= rhs.inv();
}
friend constexpr modint operator+(modint lhs, modint rhs) { return lhs += rhs; }
friend constexpr modint operator-(modint lhs, modint rhs) { return lhs -= rhs; }
friend constexpr modint operator*(modint lhs, modint rhs) { return lhs *= rhs; }
friend constexpr modint operator/(modint lhs, modint rhs) { return lhs /= rhs; }
constexpr modint operator+() const { return *this; }
constexpr modint operator-() const { return modint() - *this; }
constexpr bool operator==(const modint& rhs) const { return v == rhs.v; }
constexpr bool operator!=(const modint& rhs) const { return v != rhs.v; }
constexpr modint pow(long long p) const {
modint a(*this), res(1);
if(p < 0) {
a = a.inv();
p = -p;
}
while(p) {
if(p & 1) {
res *= a;
}
a *= a;
p >>= 1;
}
return res;
}
constexpr bool has_sqrt() const {
if(mod() == 2 || v == 0) {
return true;
}
if(pow((mod() - 1) / 2).val() != 1) {
return false;
}
return true;
}
constexpr modint sqrt() const {
if(mod() == 2 || v < 2) {
return *this;
}
assert(pow((mod() - 1) / 2).val() == 1);
modint b = 1;
while(b.pow((mod() - 1) >> 1).val() == 1) {
b += 1;
}
int m = mod() - 1, e = __builtin_ctz(m);
m >>= e;
modint x = modint(*this).pow((m - 1) >> 1);
modint y = modint(*this) * x * x;
x *= v;
modint z = b.pow(m);
while(y.val() != 1) {
int j = 0;
modint t = y;
while(t.val() != 1) {
t *= t;
j++;
}
z = z.pow(1LL << (e - j - 1));
x *= z, z *= z, y *= z;
e = j;
}
return x;
}
friend std::istream& operator>>(std::istream& in, modint& num) {
long long x;
in >> x;
num = modint<id>(x);
return in;
}
friend std::ostream& operator<<(std::ostream& out, const modint& num) {
return out << num.val();
}
public:
static std::vector<modint> fact, inv_fact, invs;
private:
int v;
static int md;
};
template<int id> int modint<id>::md = 998244353;
template<int id> std::vector<modint<id>> modint<id>::fact = {1};
template<int id> std::vector<modint<id>> modint<id>::inv_fact = {1};
template<int id> std::vector<modint<id>> modint<id>::invs = {0};
using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1000000007>;
namespace internal {
template<class T> struct is_modint : public std::false_type {};
template<int id> struct is_modint<modint<id>> : public std::true_type {};
template<class T, class ENABLE = void> struct is_static_modint : public std::false_type {};
template<int id> struct is_static_modint<modint<id>, std::enable_if_t<(id > 0)>> : public std::true_type {};
template<class T> using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template<class T, class ENABLE = void> struct is_dynamic_modint : public std::false_type {};
template<int id> struct is_dynamic_modint<modint<id>, std::enable_if_t<(id <= 0)>> : public std::true_type {};
template<class T> using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace felix