lib/math/modint.hpp

• View this file on GitHub
• Last update: 2025-05-21 23:13:24+09:00
• Include: #include "lib/math/modint.hpp"

Depends on

• Montgomery modular multiplication (lib/internal/internal_math.hpp)

Required by

• lib/algorithm/offline_binomial_sum.hpp
• 多倍長整数 (lib/data_structure/bigint.hpp)
• lib/fft/formal_power_series.hpp
• 畳み込み (lib/fft/ntt.hpp)
• 任意mod畳み込み (lib/fft/ntt_mod.hpp)
• lib/internal/internal_fft.hpp
• lib/math/bell.hpp
• Bostan-Mori法 (lib/math/bostan_mori.hpp)
• 二項係数 (lib/math/combination.hpp)
• lib/math/enumeration.hpp
• lib/math/sqrt.hpp

Verified with

• test/aoj/dpl/bell.test.cpp
• test/aoj/dpl/stirling.test.cpp
• test/aoj/jag/aho_corasick.test.cpp
• test/aoj/jag/rolling_hash.2.test.cpp
• test/aoj/ntl/addition.test.cpp
• test/aoj/ntl/difference.test.cpp
• test/aoj/ntl/division.test.cpp
• test/aoj/ntl/multiplication.test.cpp
• test/aoj/ntl/multiplication2.test.cpp
• test/aoj/ntl/power.test.cpp
• test/aoj/ntl/remainder.test.cpp
• test/yosupo/convolution/bitwise_and_convolution.test.cpp
• test/yosupo/convolution/bitwise_xor_convolution.test.cpp
• test/yosupo/convolution/convolution.test.cpp
• test/yosupo/convolution/convolution_mod.test.cpp
• test/yosupo/convolution/gcd_convolution.test.cpp
• test/yosupo/convolution/lcm_convolution.test.cpp
• test/yosupo/data_structure/addition_of_big_integers.test.cpp
• test/yosupo/data_structure/persistent_range_affine_range_sum.test.cpp
• test/yosupo/data_structure/point_set_range_composite.test.cpp
• test/yosupo/data_structure/point_set_range_composite_large_array.test.cpp
• test/yosupo/data_structure/queue_operate_all_composite.test.cpp
• test/yosupo/data_structure/range_affine_range_sum.test.cpp
• test/yosupo/data_structure/range_affine_range_sum_large_array.test.cpp
• test/yosupo/data_structure/unionfind_with_potential.test.cpp
• test/yosupo/enumerative_conbinatorics/bell_number.test.cpp
• test/yosupo/math/bostan_mori.test.cpp
• test/yosupo/math/number_of_subsequences.test.cpp
• test/yosupo/math/sqrt_mod.test.cpp
• test/yosupo/matrix/determinant_of_matrix.test.cpp
• test/yosupo/matrix/matrix_product.test.cpp
• test/yosupo/polynomial/division_of_polynomials.test.cpp
• test/yosupo/polynomial/exp_of_formal_power_series.test.cpp
• test/yosupo/polynomial/inv_of_formal_power_series.test.cpp
• test/yosupo/polynomial/log_of_formal_power_series.test.cpp
• test/yosupo/polynomial/multipoint_evaluation.test.cpp
• test/yosupo/polynomial/polynomial_interpolation.test.cpp
• test/yosupo/polynomial/polynomial_taylor_shift.test.cpp
• test/yosupo/polynomial/pow_of_formal_power_series.test.cpp
• test/yosupo/polynomial/product_of_polynomial_sequence.test.cpp
• test/yosupo/set_power_series/subset_convolution.test.cpp
• test/yosupo/tree/point_set_tree_path_composite_sum_fixed_root.test.cpp
• test/yosupo/tree/tree_path_composite_sum.test.cpp
• test/yosupo/tree/vertex_set_path_composite.test.cpp
• test/yukicoder/0551.test.cpp
• test/yukicoder/2206.test.cpp

Code

#pragma once
#include <cassert>
#include <concepts>
#include <cstdint>
#include <iostream>
#include <type_traits>
#include "internal/internal_math.hpp"

namespace internal {

struct modint_base {};
struct static_modint_base : modint_base {};

template <class T>
using is_modint = std::is_base_of<modint_base, T>;
template <class T>
using is_modint_t = std::enable_if_t<is_modint<T>::value>;

}  // namespace internal

template <int m>
requires(m >= 1)
struct static_modint : internal::static_modint_base {
    using mint = static_modint;

  public:
    static constexpr int mod() { return m; }
    static constexpr mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    constexpr static_modint() : _v(0) {}
    template <std::integral T>
    constexpr static_modint(T v) : _v(0) {
        std::int64_t x = (std::int64_t)(v % (std::int64_t)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }
    template <std::unsigned_integral T>
    constexpr static_modint(T v) : _v(0) {
        _v = (unsigned int)(v % umod());
    }

    constexpr unsigned int val() const { return _v; }

    constexpr mint &operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    constexpr mint &operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    constexpr mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    constexpr mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    constexpr mint &operator+=(const mint &rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    constexpr mint &operator-=(const mint &rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    constexpr mint &operator*=(const mint &rhs) {
        std::uint64_t z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    constexpr mint &operator/=(const mint &rhs) { return *this *= rhs.inv(); }

    constexpr mint operator+() const { return *this; }
    constexpr mint operator-() const { return mint() - *this; }

    constexpr mint pow(std::int64_t n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    constexpr mint inv() const {
        if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = internal::inv_gcd(_v, m);
            assert(eg.first == 1);
            return eg.second;
        }
    }

    friend constexpr mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
    friend constexpr mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
    friend constexpr mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
    friend constexpr mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
    friend constexpr bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; }
    friend constexpr bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; }
    friend std::istream &operator>>(std::istream &is, mint &rhs) {
        std::int64_t t;
        is >> t;
        rhs = mint(t);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const mint &rhs) { return os << rhs._v; }

  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
    static constexpr bool prime = internal::is_prime<m>;
};

template <int id>
struct dynamic_modint : internal::modint_base {
    using mint = dynamic_modint;

  public:
    static int mod() { return (int)(bt.umod()); }
    static void set_mod(int m) {
        assert(1 <= m);
        bt = internal::barrett(m);
    }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    dynamic_modint() : _v(0) {}
    template <std::integral T>
    dynamic_modint(T v) {
        std::int64_t x = (std::int64_t)(v % (std::int64_t)(mod()));
        if (x < 0) x += mod();
        _v = (unsigned int)(x);
    }
    template <std::unsigned_integral T>
    dynamic_modint(T v) {
        _v = (unsigned int)(v % mod());
    }

    unsigned int val() const { return _v; }

    mint &operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint &operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint &operator+=(const mint &rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint &operator-=(const mint &rhs) {
        _v += mod() - rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint &operator*=(const mint &rhs) {
        _v = bt.mul(_v, rhs._v);
        return *this;
    }
    mint &operator/=(const mint &rhs) { return *this *= rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(std::int64_t n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        auto eg = internal::inv_gcd(_v, mod());
        assert(eg.first == 1);
        return eg.second;
    }

    friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
    friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
    friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
    friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
    friend bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; }
    friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; }
    friend std::istream &operator>>(std::istream &is, mint &rhs) {
        std::int64_t t;
        is >> t;
        rhs = mint(t);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const mint &rhs) { return os << rhs._v; }

  private:
    unsigned int _v;
    static internal::barrett bt;
    static unsigned int umod() { return bt.umod(); }
};
template <int id>
internal::barrett dynamic_modint<id>::bt(998244353);

using modint998 = static_modint<998244353>;
using modint107 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;

namespace internal {

template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;

template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;

template <class>
struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};

template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;

}  // namespace internal

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: internal/internal_math.hpp: line -1: no such header

Back to top page