Static Modint
(lib/math/static_modint.hpp)

• View this file on GitHub
• Last update: 2024-06-15 17:22:49+08:00
• Include: #include "lib/math/static_modint.hpp"

Depends on

• Internal Definition (lib/internal.hpp)

Verified with

• verify/ds/dynamic_sequence_range_affine_range_sum_rbst.test.cpp
• verify/ds/dynamic_sequence_range_affine_range_sum_splay.test.cpp
• verify/ds/point_set_range_composite.test.cpp
• verify/math/bitwise_and_convolution.test.cpp
• verify/math/bitwise_xor_convolution.test.cpp
• verify/math/convolution.test.cpp
• verify/math/subset_convolution.test.cpp

Code

#pragma once
#include "lib/internal.hpp"

/**
 * @brief Static Modint
 *
 * @tparam M modulo
 */
template <int M> struct static_modint
{
  static constexpr u32 UM = M;
  static_assert(UM < 0x80'00'00'00u);

  u32 v;
  constexpr static_modint() : v(0) {}

  template <typename T, std::enable_if_t<std::is_signed_v<T>> * = nullptr>
  constexpr static_modint(T n) : v((n %= M) < 0 ? n + M : n)
  {
  }

  template <typename T, std::enable_if_t<std::is_unsigned_v<T>> * = nullptr>
  constexpr static_modint(T n) : v(n %= UM)
  {
  }

  using mint = static_modint;

  static mint raw(u32 v)
  {
    mint res;
    res.v = v;
    return res;
  }

  constexpr u32 val() const { return v; }

  mint operator-() const { return mint::raw(v == 0 ? 0u : UM - v); }

  mint &operator+=(mint a)
  {
    if ((v += a.v) >= UM) v -= UM;
    return *this;
  }
  mint &operator-=(mint a)
  {
    if ((v += UM - a.v) >= UM) v -= UM;
    return *this;
  }
  mint &operator*=(mint a)
  {
    v = (u64)v * a.v % UM;
    return *this;
  }
  mint &operator/=(mint a) { return *this *= a.inv(); }

  friend mint operator+(mint a, mint b) { return a += b; }
  friend mint operator-(mint a, mint b) { return a -= b; }
  friend mint operator*(mint a, mint b) { return a *= b; }
  friend mint operator/(mint a, mint b) { return a /= b; }
  friend bool operator==(mint a, mint b) { return a.val() == b.val(); }
  friend bool operator!=(mint a, mint b) { return a.val() != b.val(); }
  friend std::istream &operator>>(std::istream &in, mint x)
  {
    return in >> x.v;
  }
  friend std::ostream &operator<<(std::ostream &out, mint x)
  {
    return out << x.v;
  }

  mint pow(u64 n) const
  {
    mint res = 1, base = *this;
    while (n) {
      if (n & 1) res *= base;
      base *= base;
      n >>= 1;
    }
    return res;
  }

  mint inv() const { return pow(UM - 2); }
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: lib/internal.hpp: line 4: #pragma once found in a non-first line

Back to top page