modint/modint.hpp

• View this file on GitHub
• Last update: 2025-10-17 21:43:09+09:00
• Include: #include "modint/modint.hpp"

Required by

• 任意 mod 畳み込み (convolution/intmod.hpp)

Verified with

• verify/convolution/LC_convolution_mod.test.cpp
• verify/convolution/LC_convolution_mod_1000000007.test.cpp
• verify/convolution/LC_gcd_convolution.test.cpp
• verify/convolution/LC_lcm_convolution.test.cpp
• verify/fps/LC_composition_of_formal_power_series.test.cpp
• verify/fps/LC_composition_of_formal_power_series_large.test.cpp
• verify/fps/LC_compositional_inverse_of_formal_power_series.test.cpp
• verify/fps/LC_compositional_inverse_of_formal_power_series_large.test.cpp
• verify/fps/LC_consecutive_terms_of_linear_recurrent_sequence.test.cpp
• verify/fps/LC_convolution_mod.relaxed.test.cpp
• verify/fps/LC_convolution_mod.semirelaxed.test.cpp
• verify/fps/LC_division_of_polynomials.test.cpp
• verify/fps/LC_exp_of_formal_power_series.relaxed.test.cpp
• verify/fps/LC_exp_of_formal_power_series.test.cpp
• verify/fps/LC_exp_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_find_linear_recurrence.test.cpp
• verify/fps/LC_inv_of_formal_power_series.relaxed.test.cpp
• verify/fps/LC_inv_of_formal_power_series.test.cpp
• verify/fps/LC_inv_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_kth_term_of_linearly_recurrent_sequence.test.cpp
• verify/fps/LC_log_of_formal_power_series.relaxed.test.cpp
• verify/fps/LC_log_of_formal_power_series.test.cpp
• verify/fps/LC_log_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_multipoint_evaluation.test.cpp
• verify/fps/LC_multipoint_evaluation_on_geometric_sequence.test.cpp
• verify/fps/LC_polynomial_interpolation.test.cpp
• verify/fps/LC_polynomial_taylor_shift.test.cpp
• verify/fps/LC_pow_of_formal_power_series.test.cpp
• verify/fps/LC_pow_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_product_of_polynomial_sequence.test.cpp
• verify/fps/LC_shift_of_sampling_points_of_polynomial.test.cpp
• verify/fps/LC_sqrt_of_formal_power_series.relaxed.test.cpp
• verify/fps/LC_sqrt_of_formal_power_series.test.cpp
• verify/fps/LC_sqrt_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_sum_of_exponential_times_polynomial.test.cpp
• verify/fps/LC_sum_of_exponential_times_polynomial_limit.test.cpp
• verify/fps/UNIT_prefix_sum_of_polynomial.test.cpp
• verify/segment-tree/LC_point_set_range_composite.test.cpp
• verify/segment-tree/LC_range_affine_point_get.test.cpp
• verify/segment-tree/LC_range_affine_range_sum.test.cpp
• verify/set/LC_bitwise_and_convolution.or.test.cpp
• verify/set/LC_bitwise_and_convolution.test.cpp
• verify/set/LC_bitwise_xor_convolution.test.cpp
• verify/set/LC_exp_of_set_power_series.test.cpp
• verify/set/LC_polynomial_composite_set_power_series.test.cpp
• verify/set/LC_subset_convolution.test.cpp
• verify/set/UNIT_composite_set_power_series.test.cpp
• verify/union-find/LC_unionfind_with_potential.test.cpp

Code

#pragma once

template <unsigned int m = 998244353>
struct ModInt {
  using mint = ModInt;
  unsigned int _v;
  static constexpr unsigned int get_mod() { return m; }
  static mint raw(int v) {
    mint x;
    x._v = v;
    return x;
  }
  ModInt() : _v(0) {}
  ModInt(int64_t v) {
    long long x = (long long)(v % (long long)(umod()));
    if (x < 0) x += umod();
    _v = (unsigned int)(x);
  }
  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 -= rhs._v;
    if (_v >= umod()) _v += umod();
    return *this;
  }
  mint &operator*=(const mint &rhs) {
    unsigned long long z = _v;
    z *= rhs._v;
    _v = (unsigned int)(z % umod());
    return *this;
  }
  mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }

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

  mint pow(long long 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 {
    assert(_v);
    return pow(umod() - 2);
  }

  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 istream &operator>>(istream &is, mint &x) {
    return is >> x._v;
  }
  friend ostream &operator<<(ostream &os, const mint &x) {
    return os << x.val();
  }

 private:
  static constexpr unsigned int umod() { return m; }
};

#line 2 "modint/modint.hpp"

template <unsigned int m = 998244353>
struct ModInt {
  using mint = ModInt;
  unsigned int _v;
  static constexpr unsigned int get_mod() { return m; }
  static mint raw(int v) {
    mint x;
    x._v = v;
    return x;
  }
  ModInt() : _v(0) {}
  ModInt(int64_t v) {
    long long x = (long long)(v % (long long)(umod()));
    if (x < 0) x += umod();
    _v = (unsigned int)(x);
  }
  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 -= rhs._v;
    if (_v >= umod()) _v += umod();
    return *this;
  }
  mint &operator*=(const mint &rhs) {
    unsigned long long z = _v;
    z *= rhs._v;
    _v = (unsigned int)(z % umod());
    return *this;
  }
  mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }

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

  mint pow(long long 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 {
    assert(_v);
    return pow(umod() - 2);
  }

  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 istream &operator>>(istream &is, mint &x) {
    return is >> x._v;
  }
  friend ostream &operator<<(ostream &os, const mint &x) {
    return os << x.val();
  }

 private:
  static constexpr unsigned int umod() { return m; }
};

Back to top page