cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
Modint (for compile-time constant modulo)
(include/algebra/static_modint.hpp)
- View this file on GitHub
- Last update: 2021-10-28 01:58:02+09:00
- Include:
#include "include/algebra/static_modint.hpp"
「1000000007 で割った余りを求めよ」等の要求がある問題で使える static_modint 構造体が定義されています。演算子オーバーロードによって四則演算を行った時に指定された数で割った余りが自動的に計算されます。何で割った余りを求めるかがコンパイル時に確定しない場合(標準入力から与えられる等)には dynamic_modint を使用してください。
クラステンプレート
static_modint 構造体は 1 つの std::int_least32_t 型のテンプレート引数をとります。以下のように型エイリアスを宣言して使うとよいです。
using mint = lib::static_modint<1000000007>;
計算の高速化のために、static_modint<M> 型の 2 つの値を足し合わせても(剰余を計算する前の時点で)オーバーフローが起きない事を仮定しています。そのため、std::int_least32_t の最大値の半分を超える値をテンプレート引数に取ることはできません。
using mint = lib::static_modint<2000000000>; // 多くの環境ではエラー
この仕様でも多くの競技プログラミングの問題では困らないはずです。
$p$ が素数のとき、static_modint<p> は $0$ から $p - 1$ までの $p$ 個の元からなる剰余体 $\mathbf{Z}/p\mathbf{Z}$ を表す型として扱えます。
コンストラクタ
using mint = lib::static_modint<1000000007>;
mint a; // 1.
std::vector<mint> A(10); // 1.
mint b = 100; // 2.
mint c = 10000000000LL; // 2.
mint d(10000000000LL); // 2.
static_assert(a == 0);
assert(std::all_of(std::cbegin(A), std::cend(A), [](auto val) { val == 0; }));
static_assert(b == 100);
static_assert(c == (10000000000LL % mint::mod()));
static_assert(d == (10000000000LL % mint::mod()));
- 引数無しで初期化すると、値は 0 で初期化されます。
- 引数を 1 つ与えて初期化すると、値が代入されます。必要に応じて余りも計算されます。
演算子
以下の演算子がオーバーロードされています。
-
++(前置, 後置) -
--(前置, 後置) -
+(単項, 二項) -
-(単項, 二項) -
*(二項) /+=-=*=/===!=-
>>(std::istream&からの入力) -
<<(std::ostream&への出力)
以下の演算子もオーバーロードされていますが、デバッグレベルが $1$ 以上のとき、使用すると標準エラー出力に警告が出ます。この警告は 18 行目のコメントアウトを解除すると抑制できます。
%|^-
&(二項) -
>>(ビット演算) -
<<(ビット演算) %=|=^=&=>>=<<=><>=<=!~-
std::int_least32_t型へのキャスト
メンバ関数
以下の関数が使用できます。ここで、変数が保持している値を $x$ とします。
inv()
$x$ の乗法の逆元 $x^{-1}$ を返します。$x = 0$ である時、CP_LIBRARY_ASSERT マクロによって異常終了します。
pow(n)
$x^n$ を返します。
to_frac()
$x = a \cdot b^{-1}$ であるような $(a, b)$ の組のうち $a + b$ が最小であるものを返します。例えば $x = 2$ の時 x.inv().to_frac() は $(1, 2)$ を返します。
Verified with
- test/algebra/pow/1.test.cpp
- test/algebra/static_modint/1.test.cpp
- test/algebra/static_modint/2.test.cpp
- test/algebra/static_modint/3.test.cpp
- test/combinatorics/factorial/1.test.cpp
- test/combinatorics/factorial/2.test.cpp
- test/data_structure/binary_indexed_tree/1.test.cpp
- test/data_structure/binary_indexed_tree/2.test.cpp
Code
//! @file static_modint.hpp
#ifndef CP_LIBRARY_STATIC_MODINT_HPP
#define CP_LIBRARY_STATIC_MODINT_HPP
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <type_traits>
#define CP_LIBRARY_USE_CONSTEXPR
#ifndef CP_LIBRARY_WARN
# if (CP_LIBRARY_DEBUG_LEVEL >= 1)
//! @brief Print warning message
//! @note You can suppress the warning by uncommenting the following line
# define CP_LIBRARY_WARN(msg) (std::cerr << (msg) << '\n')
// # define CP_LIBRARY_WARN(msg) (static_cast<void>(0))
# else
# define CP_LIBRARY_WARN(msg) (static_cast<void>(0))
# undef CP_LIBRARY_USE_CONSTEXPR
# define CP_LIBRARY_USE_CONSTEXPR constexpr
# endif
# define CP_LIBRARY_WARN_NOT_DEFINED
#endif
#ifndef CP_LIBRARY_ASSERT
//! @brief Assert macro
# define CP_LIBRARY_ASSERT(...) assert(__VA_ARGS__)
# define CP_LIBRARY_ASSERT_NOT_DEFINED
#endif
namespace lib {
//! @brief modint (for compile-time constant modulo)
//! @tparam modulo modulo (e.g. 1000000007).
template <std::int_least32_t modulo,
std::enable_if_t<(1 < modulo) && (modulo < std::numeric_limits<std::int_least32_t>::max() / 2),
std::nullptr_t> = nullptr>
struct static_modint {
private:
std::int_least32_t value;
//! @param n non-zero integer
//! @return multiplicative inverse of n
template <typename Tp>
[[nodiscard]] static std::int_least32_t calc_inverse(Tp n) {
CP_LIBRARY_ASSERT(n != 0);
Tp b = modulo, u = 1, v = 0, t;
while (b > 0) {
t = n / b;
// std::swap is not necessarily constexpr in C++17
// std::swap(n -= t * b, b);
Tp tmp = std::move(n -= t * b);
n = std::move(b);
b = std::move(tmp);
// std::swap(u -= t * v, v);
tmp = std::move(u -= t * v);
u = std::move(v);
v = std::move(tmp);
}
if (u < 0)
u += modulo;
return static_cast<std::int_least32_t>(u);
}
//! @brief Calculate modulo and keep the value within [0, modulo)
//! @param v integer
//! @return integer within [0, modulo)
//! @note Time complexity: O(1)
template <typename Tp>
[[nodiscard]] static constexpr std::int_least32_t clamp_ll(Tp v) noexcept {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wsign-compare"
if (modulo <= v || v < -modulo)
v %= modulo;
#pragma GCC diagnostic pop
if (v < 0)
v += modulo;
return static_cast<std::int_least32_t>(v);
}
//! @brief Calculate modulo and keep the value within [0, modulo)
//! @note Time complexity: O(1)
constexpr void clamp_self() noexcept {
if (0 <= value) {
if (value < modulo)
return;
if (value < modulo * 2)
value -= modulo;
else
value -= modulo * 2;
} else {
if (-modulo < value)
value += modulo;
else if (-modulo * 2 < value)
value += modulo * 2;
else {
value += modulo;
value += modulo * 2;
}
}
}
public:
//! @brief underlying integer type
using type = std::int_least32_t;
//! @return modulo (e.g. 1000000007)
[[nodiscard]] static constexpr type mod() noexcept {
return modulo;
}
//! @brief Create a modint of value 0
constexpr static_modint() noexcept : value(0) {}
//! @brief Create a modint without taking modulo
constexpr static_modint(const type v, bool) noexcept : value(v) {}
//! @brief Create a modint
template <typename ValueType>
constexpr static_modint(const ValueType v) noexcept : value() {
if constexpr (std::is_integral_v<ValueType> && (std::numeric_limits<ValueType>::digits <= 32)) {
value = v;
clamp_self();
} else {
value = clamp_ll(v);
}
}
[[nodiscard]] constexpr static_modint operator+(const static_modint rhs) const noexcept {
return static_modint(value + rhs.value);
}
[[nodiscard]] constexpr static_modint operator-(const static_modint rhs) const noexcept {
return static_modint(value - rhs.value);
}
[[nodiscard]] constexpr static_modint operator*(const static_modint rhs) const noexcept {
return static_modint(static_cast<std::int_least64_t>(value) * rhs.value);
}
[[nodiscard]] static_modint operator/(const static_modint rhs) const {
return static_modint(static_cast<std::int_least64_t>(value) * calc_inverse(rhs.value));
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator%(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator% : Are you sure you want to do this?");
return static_modint(value % rhs.value);
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator&(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator& : Are you sure you want to do this?");
return static_modint(value & rhs.value, true);
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator|(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator| : Are you sure you want to do this?");
return static_modint(value | rhs.value);
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator^(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator^ : Are you sure you want to do this?");
return static_modint(value ^ rhs.value);
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator<<(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator<< : Are you sure you want to do this?");
return static_modint(static_cast<std::int_least64_t>(value) << rhs.value);
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator>>(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator>> : Are you sure you want to do this?");
return static_modint(value >> rhs.value, true);
}
constexpr static_modint& operator+=(const static_modint rhs) noexcept {
value += rhs.value;
if (value >= modulo)
value -= modulo;
return *this;
}
constexpr static_modint& operator-=(const static_modint rhs) noexcept {
value -= rhs.value;
if (value < 0)
value += modulo;
return *this;
}
constexpr static_modint& operator*=(const static_modint rhs) noexcept {
value = clamp_ll(static_cast<std::int_least64_t>(value) * rhs.value);
return *this;
}
static_modint& operator/=(const static_modint rhs) {
value = clamp_ll(static_cast<std::int_least64_t>(value) * calc_inverse(rhs.value));
return *this;
}
CP_LIBRARY_USE_CONSTEXPR static_modint& operator%=(const static_modint rhs) {
CP_LIBRARY_WARN("static_modint::operator%= : Are you sure you want to do this?");
value %= rhs.value;
if (value < 0)
value += modulo;
return *this;
}
CP_LIBRARY_USE_CONSTEXPR static_modint& operator&=(const static_modint rhs) {
CP_LIBRARY_WARN("static_modint::operator&= : Are you sure you want to do this?");
value &= rhs.value;
return *this;
}
CP_LIBRARY_USE_CONSTEXPR static_modint& operator|=(const static_modint rhs) {
CP_LIBRARY_WARN("static_modint::operator|= : Are you sure you want to do this?");
value |= rhs.value;
clamp_self();
return *this;
}
CP_LIBRARY_USE_CONSTEXPR static_modint& operator^=(const static_modint rhs) {
CP_LIBRARY_WARN("static_modint::operator^= : Are you sure you want to do this?");
value ^= rhs.value;
clamp_self();
return *this;
}
CP_LIBRARY_USE_CONSTEXPR static_modint& operator<<=(const static_modint rhs) {
CP_LIBRARY_WARN("operator<<= : Are you sure you want to do this?");
value = clamp_ll(static_cast<std::int_least64_t>(value) << rhs.value);
return *this;
}
CP_LIBRARY_USE_CONSTEXPR static_modint& operator>>=(const static_modint rhs) {
CP_LIBRARY_WARN("operator>>= : Are you sure you want to do this?");
value >>= rhs.value;
return *this;
}
template <typename RhsType>
[[nodiscard]] constexpr static_modint operator+(const RhsType rhs) const noexcept {
return static_modint(value + clamp_ll(rhs));
}
template <typename RhsType>
[[nodiscard]] constexpr static_modint operator-(const RhsType rhs) const noexcept {
return static_modint(value - clamp_ll(rhs));
}
template <typename RhsType>
[[nodiscard]] constexpr static_modint operator*(const RhsType rhs) const noexcept {
return static_modint(static_cast<std::int_least64_t>(value) * clamp_ll(rhs));
}
template <typename RhsType>
[[nodiscard]] static_modint operator/(const RhsType rhs) const {
std::int_least64_t mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);
return static_modint(value * mul);
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator%(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator% : Are you sure you want to do this?");
return static_modint(value % rhs, true);
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator&(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator& : Are you sure you want to do this?");
return static_modint(value & rhs, true);
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator|(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator| : Are you sure you want to do this?");
return static_modint(value | rhs);
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator^(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator^ : Are you sure you want to do this?");
return static_modint(value ^ rhs);
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator<<(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator<< : Are you sure you want to do this?");
return static_modint(static_cast<std::int_least64_t>(value) << rhs);
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator>>(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator>> : Are you sure you want to do this?");
return static_modint(value >> rhs, true);
}
template <typename RhsType>
constexpr static_modint& operator+=(const RhsType rhs) noexcept {
value = clamp_ll(static_cast<std::int_least64_t>(value) + rhs);
return *this;
}
template <typename RhsType>
constexpr static_modint& operator-=(const RhsType rhs) noexcept {
value = clamp_ll(static_cast<std::int_least64_t>(value) - rhs);
return *this;
}
template <typename RhsType>
constexpr static_modint& operator*=(const RhsType rhs) noexcept {
value = clamp_ll(static_cast<std::int_least64_t>(value) * clamp_ll(rhs));
return *this;
}
template <typename RhsType>
static_modint& operator/=(const RhsType rhs) {
std::int_least64_t mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);
value = clamp_ll(value * mul);
return *this;
}
template <typename RhsType>
CP_LIBRARY_USE_CONSTEXPR static_modint& operator%=(const RhsType rhs) {
CP_LIBRARY_WARN("static_modint::operator%= : Are you sure you want to do this?");
value %= rhs;
return *this;
}
template <typename RhsType>
CP_LIBRARY_USE_CONSTEXPR static_modint& operator&=(const RhsType rhs) {
CP_LIBRARY_WARN("static_modint::operator&= : Are you sure you want to do this?");
value &= rhs;
return *this;
}
template <typename RhsType>
CP_LIBRARY_USE_CONSTEXPR static_modint& operator|=(const RhsType rhs) {
CP_LIBRARY_WARN("static_modint::operator|= : Are you sure you want to do this?");
value |= rhs;
clamp_self();
return *this;
}
template <typename RhsType>
CP_LIBRARY_USE_CONSTEXPR static_modint& operator^=(const RhsType rhs) {
CP_LIBRARY_WARN("static_modint::operator^= : Are you sure you want to do this?");
value ^= rhs;
clamp_self();
return *this;
}
template <typename RhsType>
CP_LIBRARY_USE_CONSTEXPR static_modint& operator<<=(const RhsType rhs) {
CP_LIBRARY_WARN("operator<<= : Are you sure you want to do this?");
value = clamp_ll(static_cast<std::int_least64_t>(value) << rhs);
return *this;
}
template <typename RhsType>
CP_LIBRARY_USE_CONSTEXPR static_modint& operator>>=(const RhsType rhs) {
CP_LIBRARY_WARN("operator>>= : Are you sure you want to do this?");
value >>= rhs;
return *this;
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator!() const {
CP_LIBRARY_WARN("static_modint::operator! : Are you sure you want to do this?");
return value == 0;
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator~() const {
CP_LIBRARY_WARN("static_modint::operator~ : Are you sure you want to do this?");
return static_modint(~value);
}
[[nodiscard]] constexpr static_modint operator-() const noexcept {
return static_modint(value == 0 ? 0 : modulo - value, true);
}
[[nodiscard]] constexpr static_modint& operator+() const noexcept {
return *this;
}
constexpr static_modint& operator++() noexcept {
value = ((value + 1 == modulo) ? 0 : value + 1);
return *this;
}
constexpr static_modint& operator--() noexcept {
value = ((value == 0) ? modulo - 1 : value - 1);
return *this;
}
constexpr static_modint operator++(int) noexcept {
std::int_least32_t res = value;
++(*this);
return static_modint(res, true);
}
constexpr static_modint operator--(int) noexcept {
std::int_least32_t res = value;
--(*this);
return static_modint(res, true);
}
[[nodiscard]] constexpr bool operator==(const static_modint rhs) const noexcept {
return value == rhs.value;
}
[[nodiscard]] constexpr bool operator!=(const static_modint rhs) const noexcept {
return value != rhs.value;
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator< : Are you sure you want to do this?");
return value < rhs.value;
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<=(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator<= : Are you sure you want to do this?");
return value <= rhs.value;
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator> : Are you sure you want to do this?");
return value > rhs.value;
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>=(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator>= : Are you sure you want to do this?");
return value >= rhs.value;
}
template <typename RhsType>
[[nodiscard]] constexpr bool operator==(const RhsType rhs) const noexcept {
return value == rhs;
}
template <typename RhsType>
[[nodiscard]] constexpr bool operator!=(const RhsType rhs) const noexcept {
return value != rhs;
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator< : Are you sure you want to do this?");
return value < rhs;
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<=(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator<= : Are you sure you want to do this?");
return value <= rhs;
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator> : Are you sure you want to do this?");
return value > rhs;
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>=(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator>= : Are you sure you want to do this?");
return value >= rhs;
}
[[nodiscard]] constexpr operator std::int_least32_t() const {
CP_LIBRARY_WARN("A value of type static_modint has been cast to type std::int_lease32_t.");
return value;
}
//! @brief Read value (64-bit signed integer) from std::istream& is, take modulo, and store it in rhs.
//! @return std::istream& is
friend std::istream& operator>>(std::istream& is, static_modint& rhs) {
std::int_least64_t tmp;
is >> tmp;
if (tmp < -modulo || modulo <= tmp)
tmp %= modulo;
if (tmp < 0)
tmp += modulo;
rhs.value = static_cast<std::int_least32_t>(tmp);
return is;
}
//! @brief Print value to std::ostream& os
//! @return std::ostream& os
friend std::ostream& operator<<(std::ostream& os, static_modint& rhs) {
return os << rhs.value;
}
//! @return multiplicative inverse
[[nodiscard]] static_modint inv() const {
return static_modint(calc_inverse(value), true);
}
//! @tparam index_positive_guaranteed set true if and only if you can promise that index is positive
//! @tparam Tp integer type (deduced from parameter)
//! @param index index. This must be an integer, but doesn't have to be primitive.
//! @return index-th power of the value
//! @note Time complexity: O(log(index))
template <bool index_positive_guaranteed = true, typename Tp = std::int_least32_t>
[[nodiscard]] static_modint pow(Tp index) const noexcept {
if constexpr (!index_positive_guaranteed) {
if (value == 0)
return static_modint(0, true);
if (index == 0)
return static_modint(1, true);
if (index < 0)
return static_modint(value, true).inv().pow<true>(-index);
}
static_modint res(1, true), base(value, true);
while (index > 0) {
if ((index & 1) == 1)
res *= base;
base *= base;
index >>= 1;
}
return res;
}
//! @return a pair (a, b) such that b > 0, value is equal to a * (mult inverse of b), and (a + b) is minimal
[[nodiscard]] constexpr std::pair<std::int_least32_t, std::int_least32_t> to_frac() const noexcept {
std::int_least32_t x = modulo - value, y = value, u = 1, v = 1;
std::pair<std::int_least32_t, std::int_least32_t> res {value, 1};
std::int_least32_t num = value, den = 1;
std::int_least32_t cost = num + den;
while (x > 0) {
if (x <= num) {
std::int_least32_t q = num / x;
num = num % x;
den += q * u;
if (num == 0)
break;
if (num + den < cost) {
cost = num + den;
res.first = num;
res.second = den;
}
}
std::int_least32_t q = y / x;
y = y % x;
v += q * u;
q = x / y;
x = x % y;
u += q * v;
}
return res;
}
};
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] constexpr static_modint<modulo> operator+(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
return rhs + lhs;
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] constexpr static_modint<modulo> operator-(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
return -rhs + lhs;
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] constexpr static_modint<modulo> operator*(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
return rhs * lhs;
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] static_modint<modulo> operator/(const LhsType lhs, const static_modint<modulo> rhs) {
return rhs.inv() * lhs;
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint<modulo>
operator%(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator% : Are you sure you want to do this?");
return static_modint<modulo>(lhs % static_cast<std::int_least32_t>(rhs), true);
}
template <typename LhsType, std::int_least32_t modulo, std::enable_if_t<std::is_integral_v<LhsType>, std::nullptr_t> = nullptr>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint<modulo>
operator<<(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator<< : Are you sure you want to do this?");
return static_modint<modulo>(static_cast<std::int_least64_t>(lhs) << static_cast<std::int_least32_t>(rhs));
}
template <typename LhsType, std::int_least32_t modulo, std::enable_if_t<std::is_integral_v<LhsType>, std::nullptr_t> = nullptr>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint<modulo>
operator>>(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator>> : Are you sure you want to do this?");
return static_modint<modulo>(lhs >> static_cast<std::int_least32_t>(rhs));
}
template <typename LhsType, std::int_least32_t modulo>
constexpr LhsType& operator+=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
return lhs += static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
constexpr LhsType& operator-=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
return lhs -= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
constexpr LhsType& operator*=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
return lhs *= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
constexpr LhsType& operator/=(LhsType& lhs, const static_modint<modulo> rhs) {
return lhs /= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator%=(LhsType& lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator%= : Are you sure you want to do this?");
return lhs %= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator&=(LhsType& lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator&= : Are you sure you want to do this?");
return lhs &= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator|=(LhsType& lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator|= : Are you sure you want to do this?");
return lhs |= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator^=(LhsType& lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator^= : Are you sure you want to do this?");
return lhs ^= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator<<=(LhsType& lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("operator<<= : Are you sure you want to do this?");
return lhs <<= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator>>=(LhsType& lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("operator>>= : Are you sure you want to do this?");
return lhs >>= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator< : Are you sure you want to do this?");
return lhs < static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<=(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator<= : Are you sure you want to do this?");
return lhs < static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator> : Are you sure you want to do this?");
return lhs < static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>=(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator>= : Are you sure you want to do this?");
return lhs < static_cast<std::int_least32_t>(rhs);
}
} // namespace lib
#undef CP_LIBRARY_USE_CONSTEXPR
#ifdef CP_LIBRARY_WARN_NOT_DEFINED
# undef CP_LIBRARY_WARN
# undef CP_LIBRARY_WARN_NOT_DEFINED
# ifdef CP_LIBRARY_WARN
# undef CP_LIBRARY_WARN
# endif
#endif
#ifdef CP_LIBRARY_ASSERT_NOT_DEFINED
# undef CP_LIBRARY_ASSERT
# undef CP_LIBRARY_ASSERT_NOT_DEFINED
#endif
#endif // CP_LIBRARY_STATIC_MODINT_HPP#line 1 "include/algebra/static_modint.hpp"
//! @file static_modint.hpp
#ifndef CP_LIBRARY_STATIC_MODINT_HPP
#define CP_LIBRARY_STATIC_MODINT_HPP
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <type_traits>
#define CP_LIBRARY_USE_CONSTEXPR
#ifndef CP_LIBRARY_WARN
# if (CP_LIBRARY_DEBUG_LEVEL >= 1)
//! @brief Print warning message
//! @note You can suppress the warning by uncommenting the following line
# define CP_LIBRARY_WARN(msg) (std::cerr << (msg) << '\n')
// # define CP_LIBRARY_WARN(msg) (static_cast<void>(0))
# else
# define CP_LIBRARY_WARN(msg) (static_cast<void>(0))
# undef CP_LIBRARY_USE_CONSTEXPR
# define CP_LIBRARY_USE_CONSTEXPR constexpr
# endif
# define CP_LIBRARY_WARN_NOT_DEFINED
#endif
#ifndef CP_LIBRARY_ASSERT
//! @brief Assert macro
# define CP_LIBRARY_ASSERT(...) assert(__VA_ARGS__)
# define CP_LIBRARY_ASSERT_NOT_DEFINED
#endif
namespace lib {
//! @brief modint (for compile-time constant modulo)
//! @tparam modulo modulo (e.g. 1000000007).
template <std::int_least32_t modulo,
std::enable_if_t<(1 < modulo) && (modulo < std::numeric_limits<std::int_least32_t>::max() / 2),
std::nullptr_t> = nullptr>
struct static_modint {
private:
std::int_least32_t value;
//! @param n non-zero integer
//! @return multiplicative inverse of n
template <typename Tp>
[[nodiscard]] static std::int_least32_t calc_inverse(Tp n) {
CP_LIBRARY_ASSERT(n != 0);
Tp b = modulo, u = 1, v = 0, t;
while (b > 0) {
t = n / b;
// std::swap is not necessarily constexpr in C++17
// std::swap(n -= t * b, b);
Tp tmp = std::move(n -= t * b);
n = std::move(b);
b = std::move(tmp);
// std::swap(u -= t * v, v);
tmp = std::move(u -= t * v);
u = std::move(v);
v = std::move(tmp);
}
if (u < 0)
u += modulo;
return static_cast<std::int_least32_t>(u);
}
//! @brief Calculate modulo and keep the value within [0, modulo)
//! @param v integer
//! @return integer within [0, modulo)
//! @note Time complexity: O(1)
template <typename Tp>
[[nodiscard]] static constexpr std::int_least32_t clamp_ll(Tp v) noexcept {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wsign-compare"
if (modulo <= v || v < -modulo)
v %= modulo;
#pragma GCC diagnostic pop
if (v < 0)
v += modulo;
return static_cast<std::int_least32_t>(v);
}
//! @brief Calculate modulo and keep the value within [0, modulo)
//! @note Time complexity: O(1)
constexpr void clamp_self() noexcept {
if (0 <= value) {
if (value < modulo)
return;
if (value < modulo * 2)
value -= modulo;
else
value -= modulo * 2;
} else {
if (-modulo < value)
value += modulo;
else if (-modulo * 2 < value)
value += modulo * 2;
else {
value += modulo;
value += modulo * 2;
}
}
}
public:
//! @brief underlying integer type
using type = std::int_least32_t;
//! @return modulo (e.g. 1000000007)
[[nodiscard]] static constexpr type mod() noexcept {
return modulo;
}
//! @brief Create a modint of value 0
constexpr static_modint() noexcept : value(0) {}
//! @brief Create a modint without taking modulo
constexpr static_modint(const type v, bool) noexcept : value(v) {}
//! @brief Create a modint
template <typename ValueType>
constexpr static_modint(const ValueType v) noexcept : value() {
if constexpr (std::is_integral_v<ValueType> && (std::numeric_limits<ValueType>::digits <= 32)) {
value = v;
clamp_self();
} else {
value = clamp_ll(v);
}
}
[[nodiscard]] constexpr static_modint operator+(const static_modint rhs) const noexcept {
return static_modint(value + rhs.value);
}
[[nodiscard]] constexpr static_modint operator-(const static_modint rhs) const noexcept {
return static_modint(value - rhs.value);
}
[[nodiscard]] constexpr static_modint operator*(const static_modint rhs) const noexcept {
return static_modint(static_cast<std::int_least64_t>(value) * rhs.value);
}
[[nodiscard]] static_modint operator/(const static_modint rhs) const {
return static_modint(static_cast<std::int_least64_t>(value) * calc_inverse(rhs.value));
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator%(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator% : Are you sure you want to do this?");
return static_modint(value % rhs.value);
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator&(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator& : Are you sure you want to do this?");
return static_modint(value & rhs.value, true);
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator|(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator| : Are you sure you want to do this?");
return static_modint(value | rhs.value);
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator^(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator^ : Are you sure you want to do this?");
return static_modint(value ^ rhs.value);
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator<<(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator<< : Are you sure you want to do this?");
return static_modint(static_cast<std::int_least64_t>(value) << rhs.value);
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator>>(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator>> : Are you sure you want to do this?");
return static_modint(value >> rhs.value, true);
}
constexpr static_modint& operator+=(const static_modint rhs) noexcept {
value += rhs.value;
if (value >= modulo)
value -= modulo;
return *this;
}
constexpr static_modint& operator-=(const static_modint rhs) noexcept {
value -= rhs.value;
if (value < 0)
value += modulo;
return *this;
}
constexpr static_modint& operator*=(const static_modint rhs) noexcept {
value = clamp_ll(static_cast<std::int_least64_t>(value) * rhs.value);
return *this;
}
static_modint& operator/=(const static_modint rhs) {
value = clamp_ll(static_cast<std::int_least64_t>(value) * calc_inverse(rhs.value));
return *this;
}
CP_LIBRARY_USE_CONSTEXPR static_modint& operator%=(const static_modint rhs) {
CP_LIBRARY_WARN("static_modint::operator%= : Are you sure you want to do this?");
value %= rhs.value;
if (value < 0)
value += modulo;
return *this;
}
CP_LIBRARY_USE_CONSTEXPR static_modint& operator&=(const static_modint rhs) {
CP_LIBRARY_WARN("static_modint::operator&= : Are you sure you want to do this?");
value &= rhs.value;
return *this;
}
CP_LIBRARY_USE_CONSTEXPR static_modint& operator|=(const static_modint rhs) {
CP_LIBRARY_WARN("static_modint::operator|= : Are you sure you want to do this?");
value |= rhs.value;
clamp_self();
return *this;
}
CP_LIBRARY_USE_CONSTEXPR static_modint& operator^=(const static_modint rhs) {
CP_LIBRARY_WARN("static_modint::operator^= : Are you sure you want to do this?");
value ^= rhs.value;
clamp_self();
return *this;
}
CP_LIBRARY_USE_CONSTEXPR static_modint& operator<<=(const static_modint rhs) {
CP_LIBRARY_WARN("operator<<= : Are you sure you want to do this?");
value = clamp_ll(static_cast<std::int_least64_t>(value) << rhs.value);
return *this;
}
CP_LIBRARY_USE_CONSTEXPR static_modint& operator>>=(const static_modint rhs) {
CP_LIBRARY_WARN("operator>>= : Are you sure you want to do this?");
value >>= rhs.value;
return *this;
}
template <typename RhsType>
[[nodiscard]] constexpr static_modint operator+(const RhsType rhs) const noexcept {
return static_modint(value + clamp_ll(rhs));
}
template <typename RhsType>
[[nodiscard]] constexpr static_modint operator-(const RhsType rhs) const noexcept {
return static_modint(value - clamp_ll(rhs));
}
template <typename RhsType>
[[nodiscard]] constexpr static_modint operator*(const RhsType rhs) const noexcept {
return static_modint(static_cast<std::int_least64_t>(value) * clamp_ll(rhs));
}
template <typename RhsType>
[[nodiscard]] static_modint operator/(const RhsType rhs) const {
std::int_least64_t mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);
return static_modint(value * mul);
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator%(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator% : Are you sure you want to do this?");
return static_modint(value % rhs, true);
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator&(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator& : Are you sure you want to do this?");
return static_modint(value & rhs, true);
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator|(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator| : Are you sure you want to do this?");
return static_modint(value | rhs);
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator^(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator^ : Are you sure you want to do this?");
return static_modint(value ^ rhs);
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator<<(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator<< : Are you sure you want to do this?");
return static_modint(static_cast<std::int_least64_t>(value) << rhs);
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator>>(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator>> : Are you sure you want to do this?");
return static_modint(value >> rhs, true);
}
template <typename RhsType>
constexpr static_modint& operator+=(const RhsType rhs) noexcept {
value = clamp_ll(static_cast<std::int_least64_t>(value) + rhs);
return *this;
}
template <typename RhsType>
constexpr static_modint& operator-=(const RhsType rhs) noexcept {
value = clamp_ll(static_cast<std::int_least64_t>(value) - rhs);
return *this;
}
template <typename RhsType>
constexpr static_modint& operator*=(const RhsType rhs) noexcept {
value = clamp_ll(static_cast<std::int_least64_t>(value) * clamp_ll(rhs));
return *this;
}
template <typename RhsType>
static_modint& operator/=(const RhsType rhs) {
std::int_least64_t mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);
value = clamp_ll(value * mul);
return *this;
}
template <typename RhsType>
CP_LIBRARY_USE_CONSTEXPR static_modint& operator%=(const RhsType rhs) {
CP_LIBRARY_WARN("static_modint::operator%= : Are you sure you want to do this?");
value %= rhs;
return *this;
}
template <typename RhsType>
CP_LIBRARY_USE_CONSTEXPR static_modint& operator&=(const RhsType rhs) {
CP_LIBRARY_WARN("static_modint::operator&= : Are you sure you want to do this?");
value &= rhs;
return *this;
}
template <typename RhsType>
CP_LIBRARY_USE_CONSTEXPR static_modint& operator|=(const RhsType rhs) {
CP_LIBRARY_WARN("static_modint::operator|= : Are you sure you want to do this?");
value |= rhs;
clamp_self();
return *this;
}
template <typename RhsType>
CP_LIBRARY_USE_CONSTEXPR static_modint& operator^=(const RhsType rhs) {
CP_LIBRARY_WARN("static_modint::operator^= : Are you sure you want to do this?");
value ^= rhs;
clamp_self();
return *this;
}
template <typename RhsType>
CP_LIBRARY_USE_CONSTEXPR static_modint& operator<<=(const RhsType rhs) {
CP_LIBRARY_WARN("operator<<= : Are you sure you want to do this?");
value = clamp_ll(static_cast<std::int_least64_t>(value) << rhs);
return *this;
}
template <typename RhsType>
CP_LIBRARY_USE_CONSTEXPR static_modint& operator>>=(const RhsType rhs) {
CP_LIBRARY_WARN("operator>>= : Are you sure you want to do this?");
value >>= rhs;
return *this;
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator!() const {
CP_LIBRARY_WARN("static_modint::operator! : Are you sure you want to do this?");
return value == 0;
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator~() const {
CP_LIBRARY_WARN("static_modint::operator~ : Are you sure you want to do this?");
return static_modint(~value);
}
[[nodiscard]] constexpr static_modint operator-() const noexcept {
return static_modint(value == 0 ? 0 : modulo - value, true);
}
[[nodiscard]] constexpr static_modint& operator+() const noexcept {
return *this;
}
constexpr static_modint& operator++() noexcept {
value = ((value + 1 == modulo) ? 0 : value + 1);
return *this;
}
constexpr static_modint& operator--() noexcept {
value = ((value == 0) ? modulo - 1 : value - 1);
return *this;
}
constexpr static_modint operator++(int) noexcept {
std::int_least32_t res = value;
++(*this);
return static_modint(res, true);
}
constexpr static_modint operator--(int) noexcept {
std::int_least32_t res = value;
--(*this);
return static_modint(res, true);
}
[[nodiscard]] constexpr bool operator==(const static_modint rhs) const noexcept {
return value == rhs.value;
}
[[nodiscard]] constexpr bool operator!=(const static_modint rhs) const noexcept {
return value != rhs.value;
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator< : Are you sure you want to do this?");
return value < rhs.value;
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<=(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator<= : Are you sure you want to do this?");
return value <= rhs.value;
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator> : Are you sure you want to do this?");
return value > rhs.value;
}
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>=(const static_modint rhs) const {
CP_LIBRARY_WARN("static_modint::operator>= : Are you sure you want to do this?");
return value >= rhs.value;
}
template <typename RhsType>
[[nodiscard]] constexpr bool operator==(const RhsType rhs) const noexcept {
return value == rhs;
}
template <typename RhsType>
[[nodiscard]] constexpr bool operator!=(const RhsType rhs) const noexcept {
return value != rhs;
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator< : Are you sure you want to do this?");
return value < rhs;
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<=(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator<= : Are you sure you want to do this?");
return value <= rhs;
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator> : Are you sure you want to do this?");
return value > rhs;
}
template <typename RhsType>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>=(const RhsType rhs) const {
CP_LIBRARY_WARN("static_modint::operator>= : Are you sure you want to do this?");
return value >= rhs;
}
[[nodiscard]] constexpr operator std::int_least32_t() const {
CP_LIBRARY_WARN("A value of type static_modint has been cast to type std::int_lease32_t.");
return value;
}
//! @brief Read value (64-bit signed integer) from std::istream& is, take modulo, and store it in rhs.
//! @return std::istream& is
friend std::istream& operator>>(std::istream& is, static_modint& rhs) {
std::int_least64_t tmp;
is >> tmp;
if (tmp < -modulo || modulo <= tmp)
tmp %= modulo;
if (tmp < 0)
tmp += modulo;
rhs.value = static_cast<std::int_least32_t>(tmp);
return is;
}
//! @brief Print value to std::ostream& os
//! @return std::ostream& os
friend std::ostream& operator<<(std::ostream& os, static_modint& rhs) {
return os << rhs.value;
}
//! @return multiplicative inverse
[[nodiscard]] static_modint inv() const {
return static_modint(calc_inverse(value), true);
}
//! @tparam index_positive_guaranteed set true if and only if you can promise that index is positive
//! @tparam Tp integer type (deduced from parameter)
//! @param index index. This must be an integer, but doesn't have to be primitive.
//! @return index-th power of the value
//! @note Time complexity: O(log(index))
template <bool index_positive_guaranteed = true, typename Tp = std::int_least32_t>
[[nodiscard]] static_modint pow(Tp index) const noexcept {
if constexpr (!index_positive_guaranteed) {
if (value == 0)
return static_modint(0, true);
if (index == 0)
return static_modint(1, true);
if (index < 0)
return static_modint(value, true).inv().pow<true>(-index);
}
static_modint res(1, true), base(value, true);
while (index > 0) {
if ((index & 1) == 1)
res *= base;
base *= base;
index >>= 1;
}
return res;
}
//! @return a pair (a, b) such that b > 0, value is equal to a * (mult inverse of b), and (a + b) is minimal
[[nodiscard]] constexpr std::pair<std::int_least32_t, std::int_least32_t> to_frac() const noexcept {
std::int_least32_t x = modulo - value, y = value, u = 1, v = 1;
std::pair<std::int_least32_t, std::int_least32_t> res {value, 1};
std::int_least32_t num = value, den = 1;
std::int_least32_t cost = num + den;
while (x > 0) {
if (x <= num) {
std::int_least32_t q = num / x;
num = num % x;
den += q * u;
if (num == 0)
break;
if (num + den < cost) {
cost = num + den;
res.first = num;
res.second = den;
}
}
std::int_least32_t q = y / x;
y = y % x;
v += q * u;
q = x / y;
x = x % y;
u += q * v;
}
return res;
}
};
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] constexpr static_modint<modulo> operator+(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
return rhs + lhs;
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] constexpr static_modint<modulo> operator-(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
return -rhs + lhs;
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] constexpr static_modint<modulo> operator*(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
return rhs * lhs;
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] static_modint<modulo> operator/(const LhsType lhs, const static_modint<modulo> rhs) {
return rhs.inv() * lhs;
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint<modulo>
operator%(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator% : Are you sure you want to do this?");
return static_modint<modulo>(lhs % static_cast<std::int_least32_t>(rhs), true);
}
template <typename LhsType, std::int_least32_t modulo, std::enable_if_t<std::is_integral_v<LhsType>, std::nullptr_t> = nullptr>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint<modulo>
operator<<(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator<< : Are you sure you want to do this?");
return static_modint<modulo>(static_cast<std::int_least64_t>(lhs) << static_cast<std::int_least32_t>(rhs));
}
template <typename LhsType, std::int_least32_t modulo, std::enable_if_t<std::is_integral_v<LhsType>, std::nullptr_t> = nullptr>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint<modulo>
operator>>(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator>> : Are you sure you want to do this?");
return static_modint<modulo>(lhs >> static_cast<std::int_least32_t>(rhs));
}
template <typename LhsType, std::int_least32_t modulo>
constexpr LhsType& operator+=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
return lhs += static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
constexpr LhsType& operator-=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
return lhs -= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
constexpr LhsType& operator*=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
return lhs *= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
constexpr LhsType& operator/=(LhsType& lhs, const static_modint<modulo> rhs) {
return lhs /= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator%=(LhsType& lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator%= : Are you sure you want to do this?");
return lhs %= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator&=(LhsType& lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator&= : Are you sure you want to do this?");
return lhs &= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator|=(LhsType& lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator|= : Are you sure you want to do this?");
return lhs |= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator^=(LhsType& lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator^= : Are you sure you want to do this?");
return lhs ^= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator<<=(LhsType& lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("operator<<= : Are you sure you want to do this?");
return lhs <<= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator>>=(LhsType& lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("operator>>= : Are you sure you want to do this?");
return lhs >>= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator< : Are you sure you want to do this?");
return lhs < static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<=(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator<= : Are you sure you want to do this?");
return lhs < static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator> : Are you sure you want to do this?");
return lhs < static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>=(const LhsType lhs, const static_modint<modulo> rhs) {
CP_LIBRARY_WARN("static_modint::operator>= : Are you sure you want to do this?");
return lhs < static_cast<std::int_least32_t>(rhs);
}
} // namespace lib
#undef CP_LIBRARY_USE_CONSTEXPR
#ifdef CP_LIBRARY_WARN_NOT_DEFINED
# undef CP_LIBRARY_WARN
# undef CP_LIBRARY_WARN_NOT_DEFINED
# ifdef CP_LIBRARY_WARN
# undef CP_LIBRARY_WARN
# endif
#endif
#ifdef CP_LIBRARY_ASSERT_NOT_DEFINED
# undef CP_LIBRARY_ASSERT
# undef CP_LIBRARY_ASSERT_NOT_DEFINED
#endif
#endif // CP_LIBRARY_STATIC_MODINT_HPP