modint.hpp

• View this file on GitHub
• Last update: 2025-01-19 15:28:01+08:00
• Include: #include "modint.hpp"

Verified with

• test/convolution/2d_convolution.0.test.cpp
• test/convolution/bitwise_and_convolution.0.test.cpp
• test/convolution/bitwise_xor_convolution.0.test.cpp
• test/convolution/convolution_mod.0.test.cpp
• test/convolution/multidimensional_convolution.0.test.cpp
• test/data_structure/dynamic_sequence_range_affine_range_sum.0.test.cpp
• test/data_structure/point_set_range_composite.0.test.cpp
• test/data_structure/queue_operate_all_composite.0.test.cpp
• test/data_structure/range_affine_point_get.0.test.cpp
• test/data_structure/range_affine_range_sum.0.test.cpp
• test/enumerative_combinatorics/bell_number.0.test.cpp
• test/enumerative_combinatorics/factorial.0.test.cpp
• test/enumerative_combinatorics/partition_function.0.test.cpp
• test/enumerative_combinatorics/sharp_p_subset_sum.0.test.cpp
• test/enumerative_combinatorics/stirling_number_of_the_first_kind.0.test.cpp
• test/enumerative_combinatorics/stirling_number_of_the_first_kind_fixed_k.0.test.cpp
• test/enumerative_combinatorics/stirling_number_of_the_second_kind.0.test.cpp
• test/enumerative_combinatorics/stirling_number_of_the_second_kind_fixed_k.0.test.cpp
• test/formal_power_series/composition_of_formal_power_series_large.0.test.cpp
• test/formal_power_series/compositional_inverse_of_formal_power_series_large.0.test.cpp
• test/formal_power_series/consecutive_terms_of_linear_recurrent_sequence.0.test.cpp
• test/formal_power_series/conversion_from_monomial_basis_to_newton_basis.0.test.cpp
• test/formal_power_series/division_of_polynomials.0.test.cpp
• test/formal_power_series/exp_of_formal_power_series.0.test.cpp
• test/formal_power_series/find_linear_recurrence.0.test.cpp
• test/formal_power_series/inv_of_formal_power_series.0.test.cpp
• test/formal_power_series/inv_of_formal_power_series.1.test.cpp
• test/formal_power_series/inv_of_polynomials.0.test.cpp
• test/formal_power_series/kth_term_of_linearly_recurrent_sequence.0.test.cpp
• test/formal_power_series/log_of_formal_power_series.0.test.cpp
• test/formal_power_series/multipoint_evaluation.0.test.cpp
• test/formal_power_series/multipoint_evaluation_on_geometric_sequence.0.test.cpp
• test/formal_power_series/multivariate_power_series.0.test.cpp
• test/formal_power_series/polynomial_interpolation.0.test.cpp
• test/formal_power_series/polynomial_interpolation_on_geometric_sequence.0.test.cpp
• test/formal_power_series/polynomial_taylor_shift.0.test.cpp
• test/formal_power_series/polynomial_taylor_shift.1.test.cpp
• test/formal_power_series/pow_of_formal_power_series.0.test.cpp
• test/formal_power_series/product_of_polynomial_sequence.0.test.cpp
• test/formal_power_series/shift_of_sampling_points_of_polynomial.0.test.cpp
• test/formal_power_series/shift_of_sampling_points_of_polynomial.1.test.cpp
• test/formal_power_series/sqrt_of_formal_power_series.0.test.cpp
• test/matrix/adjugate_matrix.0.test.cpp
• test/matrix/characteristic_polynomial.0.test.cpp
• test/matrix/characteristic_polynomial.1.test.cpp
• test/matrix/inverse_matrix.0.test.cpp
• test/matrix/matrix_det.0.test.cpp
• test/matrix/matrix_product.0.test.cpp
• test/matrix/pow_of_matrix.0.test.cpp
• test/matrix/sparse_matrix_det.0.test.cpp
• test/set_power_series/exp_of_set_power_series.0.test.cpp
• test/set_power_series/inv_of_set_power_series.0.test.cpp
• test/set_power_series/log_of_set_power_series.0.test.cpp
• test/set_power_series/polynomial_composite_set_power_series.0.test.cpp
• test/set_power_series/subset_convolution.0.test.cpp

Code

#pragma once

#include <iostream>
#include <type_traits>

// clang-format off
template<unsigned Mod> class ModInt {
    static_assert((Mod >> 31) == 0, "`Mod` must less than 2^(31)");
    template<typename Int>
    static std::enable_if_t<std::is_integral_v<Int>, unsigned> safe_mod(Int v) { using D = std::common_type_t<Int, unsigned>; return (v %= (int)Mod) < 0 ? (D)(v + (int)Mod) : (D)v; }
    struct PrivateConstructor {} static inline private_constructor{};
    ModInt(PrivateConstructor, unsigned v) : v_(v) {}
    unsigned v_;

public:
    static unsigned mod() { return Mod; }
    static ModInt from_raw(unsigned v) { return ModInt(private_constructor, v); }
    static ModInt zero() { return from_raw(0); }
    static ModInt one() { return from_raw(1); }
    bool is_zero() const { return v_ == 0; }
    bool is_one() const { return v_ == 1; }
    ModInt() : v_() {}
    template<typename Int, typename std::enable_if_t<std::is_signed_v<Int>, int> = 0> ModInt(Int v) : v_(safe_mod(v)) {}
    template<typename Int, typename std::enable_if_t<std::is_unsigned_v<Int>, int> = 0> ModInt(Int v) : v_(v % Mod) {}
    unsigned val() const { return v_; }
    ModInt operator-() const { return from_raw(v_ == 0 ? v_ : Mod - v_); }
    ModInt pow(long long e) const { if (e < 0) return inv().pow(-e); for (ModInt x(*this), res(from_raw(1));; x *= x) { if (e & 1) res *= x; if ((e >>= 1) == 0) return res; }}
    ModInt inv() const { int x1 = 1, x3 = 0, a = val(), b = Mod; while (b) { const int q = a / b, x1_old = x1, a_old = a; x1 = x3, x3 = x1_old - x3 * q, a = b, b = a_old - b * q; } return from_raw(x1 < 0 ? x1 + (int)Mod : x1); }
    template<bool Odd = (Mod & 1)> std::enable_if_t<Odd, ModInt> div_by_2() const { if (v_ & 1) return from_raw((v_ + Mod) >> 1); return from_raw(v_ >> 1); }
    ModInt &operator+=(const ModInt &a) { if ((v_ += a.v_) >= Mod) v_ -= Mod; return *this; }
    ModInt &operator-=(const ModInt &a) { if ((v_ += Mod - a.v_) >= Mod) v_ -= Mod; return *this; }
    ModInt &operator*=(const ModInt &a) { v_ = (unsigned long long)v_ * a.v_ % Mod; return *this; }
    ModInt &operator/=(const ModInt &a) { return *this *= a.inv(); }
    ModInt &operator++() { return *this += one(); }
    ModInt operator++(int) { ModInt o(*this); *this += one(); return o; }
    ModInt &operator--() { return *this -= one(); }
    ModInt operator--(int) { ModInt o(*this); *this -= one(); return o; }
    friend ModInt operator+(const ModInt &a, const ModInt &b) { return ModInt(a) += b; }
    friend ModInt operator-(const ModInt &a, const ModInt &b) { return ModInt(a) -= b; }
    friend ModInt operator*(const ModInt &a, const ModInt &b) { return ModInt(a) *= b; }
    friend ModInt operator/(const ModInt &a, const ModInt &b) { return ModInt(a) /= b; }
    friend bool operator==(const ModInt &a, const ModInt &b) { return a.v_ == b.v_; }
    friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v_ != b.v_; }
    friend std::istream &operator>>(std::istream &a, ModInt &b) { int v; a >> v; b.v_ = safe_mod(v); return a; }
    friend std::ostream &operator<<(std::ostream &a, const ModInt &b) { return a << b.val(); }
};
// clang-format on

#line 2 "modint.hpp"

#include <iostream>
#include <type_traits>

// clang-format off
template<unsigned Mod> class ModInt {
    static_assert((Mod >> 31) == 0, "`Mod` must less than 2^(31)");
    template<typename Int>
    static std::enable_if_t<std::is_integral_v<Int>, unsigned> safe_mod(Int v) { using D = std::common_type_t<Int, unsigned>; return (v %= (int)Mod) < 0 ? (D)(v + (int)Mod) : (D)v; }
    struct PrivateConstructor {} static inline private_constructor{};
    ModInt(PrivateConstructor, unsigned v) : v_(v) {}
    unsigned v_;

public:
    static unsigned mod() { return Mod; }
    static ModInt from_raw(unsigned v) { return ModInt(private_constructor, v); }
    static ModInt zero() { return from_raw(0); }
    static ModInt one() { return from_raw(1); }
    bool is_zero() const { return v_ == 0; }
    bool is_one() const { return v_ == 1; }
    ModInt() : v_() {}
    template<typename Int, typename std::enable_if_t<std::is_signed_v<Int>, int> = 0> ModInt(Int v) : v_(safe_mod(v)) {}
    template<typename Int, typename std::enable_if_t<std::is_unsigned_v<Int>, int> = 0> ModInt(Int v) : v_(v % Mod) {}
    unsigned val() const { return v_; }
    ModInt operator-() const { return from_raw(v_ == 0 ? v_ : Mod - v_); }
    ModInt pow(long long e) const { if (e < 0) return inv().pow(-e); for (ModInt x(*this), res(from_raw(1));; x *= x) { if (e & 1) res *= x; if ((e >>= 1) == 0) return res; }}
    ModInt inv() const { int x1 = 1, x3 = 0, a = val(), b = Mod; while (b) { const int q = a / b, x1_old = x1, a_old = a; x1 = x3, x3 = x1_old - x3 * q, a = b, b = a_old - b * q; } return from_raw(x1 < 0 ? x1 + (int)Mod : x1); }
    template<bool Odd = (Mod & 1)> std::enable_if_t<Odd, ModInt> div_by_2() const { if (v_ & 1) return from_raw((v_ + Mod) >> 1); return from_raw(v_ >> 1); }
    ModInt &operator+=(const ModInt &a) { if ((v_ += a.v_) >= Mod) v_ -= Mod; return *this; }
    ModInt &operator-=(const ModInt &a) { if ((v_ += Mod - a.v_) >= Mod) v_ -= Mod; return *this; }
    ModInt &operator*=(const ModInt &a) { v_ = (unsigned long long)v_ * a.v_ % Mod; return *this; }
    ModInt &operator/=(const ModInt &a) { return *this *= a.inv(); }
    ModInt &operator++() { return *this += one(); }
    ModInt operator++(int) { ModInt o(*this); *this += one(); return o; }
    ModInt &operator--() { return *this -= one(); }
    ModInt operator--(int) { ModInt o(*this); *this -= one(); return o; }
    friend ModInt operator+(const ModInt &a, const ModInt &b) { return ModInt(a) += b; }
    friend ModInt operator-(const ModInt &a, const ModInt &b) { return ModInt(a) -= b; }
    friend ModInt operator*(const ModInt &a, const ModInt &b) { return ModInt(a) *= b; }
    friend ModInt operator/(const ModInt &a, const ModInt &b) { return ModInt(a) /= b; }
    friend bool operator==(const ModInt &a, const ModInt &b) { return a.v_ == b.v_; }
    friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v_ != b.v_; }
    friend std::istream &operator>>(std::istream &a, ModInt &b) { int v; a >> v; b.v_ = safe_mod(v); return a; }
    friend std::ostream &operator<<(std::ostream &a, const ModInt &b) { return a << b.val(); }
};
// clang-format on

Back to top page