mod/modint61.hpp

• View this file on GitHub
• Last update: 2024-08-27 05:16:49+09:00
• Include: #include "mod/modint61.hpp"

Required by

• alg/monoid/rollinghash.hpp
• graph/ds/rolling_hash_on_tree.hpp
• graph/maximum_matching_size.hpp
• graph/tree_dp/subtree_hash.hpp
• mod/modular_subset_sum.hpp
• other/connected_dp.hpp
• random/hash_vector.hpp
• string/basic_substring_structure.hpp
• string/deque_rolling_hash.hpp
• string/rollinghash.hpp
• string/rollinghash_2d.hpp
• string/substring_count_in_substring.hpp

Verified with

• test/1_mytest/enumerate_unlabeled_tree.test.cpp
• test/1_mytest/matching.test.cpp
• test/1_mytest/matching_line_graph.test.cpp
• test/1_mytest/rolling_hash_on_tree.test.cpp
• test/1_mytest/tdpc_grid_dp.test.cpp
• test/1_mytest/tutte.test.cpp
• test/2_library_checker/graph/classify_tree.test.cpp
• test/2_library_checker/graph/general_matching.test.cpp
• test/2_library_checker/string/zalgorithm_by_rollinghash.test.cpp
• test/2_library_checker/string/zalgorithm_by_rollinghash2.test.cpp
• test/3_yukicoder/1397.test.cpp
• test/3_yukicoder/1561.test.cpp
• test/3_yukicoder/1881.test.cpp
• test/3_yukicoder/2102.test.cpp
• test/3_yukicoder/2231.test.cpp
• test/3_yukicoder/2626.test.cpp
• test/3_yukicoder/263.test.cpp
• test/3_yukicoder/4_1.test.cpp
• test/3_yukicoder/541.test.cpp
• test/3_yukicoder/578.test.cpp
• test/3_yukicoder/579.test.cpp
• test/4_aoj/ALDS1_14_C.test.cpp

Code

#pragma once

struct modint61 {
  static constexpr u64 mod = (1ULL << 61) - 1;
  u64 val;
  constexpr modint61() : val(0ULL) {}
  constexpr modint61(u32 x) : val(x) {}
  constexpr modint61(u64 x) : val(x % mod) {}
  constexpr modint61(int x) : val((x < 0) ? (x + static_cast<ll>(mod)) : x) {}
  constexpr modint61(ll x) : val(((x %= static_cast<ll>(mod)) < 0) ? (x + static_cast<ll>(mod)) : x) {}
  static constexpr u64 get_mod() { return mod; }

  modint61 &operator+=(const modint61 &a) {
    val = ((val += a.val) >= mod) ? (val - mod) : val;
    return *this;
  }
  modint61 &operator-=(const modint61 &a) {
    val = ((val -= a.val) >= mod) ? (val + mod) : val;
    return *this;
  }
  modint61 &operator*=(const modint61 &a) {
    const unsigned __int128 y = static_cast<unsigned __int128>(val) * a.val;
    val = (y >> 61) + (y & mod);
    val = (val >= mod) ? (val - mod) : val;
    return *this;
  }
  modint61 operator-() const { return modint61(val ? mod - val : u64(0)); }
  modint61 &operator/=(const modint61 &a) { return (*this *= a.inverse()); }
  modint61 operator+(const modint61 &p) const { return modint61(*this) += p; }
  modint61 operator-(const modint61 &p) const { return modint61(*this) -= p; }
  modint61 operator*(const modint61 &p) const { return modint61(*this) *= p; }
  modint61 operator/(const modint61 &p) const { return modint61(*this) /= p; }
  bool operator<(const modint61 &other) const { return val < other.val; }
  bool operator==(const modint61 &p) const { return val == p.val; }
  bool operator!=(const modint61 &p) const { return val != p.val; }
  modint61 inverse() const {
    ll a = val, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b), swap(u -= t * v, v);
    }
    return modint61(u);
  }
  modint61 pow(ll n) const {
    assert(n >= 0);
    modint61 ret(1), mul(val);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul, n >>= 1;
    }
    return ret;
  }
};

#ifdef FASTIO
void rd(modint61 &x) {
  fastio::rd(x.val);
  assert(0 <= x.val && x.val < modint61::mod);
}

void wt(modint61 x) { fastio::wt(x.val); }
#endif

#line 2 "mod/modint61.hpp"

struct modint61 {
  static constexpr u64 mod = (1ULL << 61) - 1;
  u64 val;
  constexpr modint61() : val(0ULL) {}
  constexpr modint61(u32 x) : val(x) {}
  constexpr modint61(u64 x) : val(x % mod) {}
  constexpr modint61(int x) : val((x < 0) ? (x + static_cast<ll>(mod)) : x) {}
  constexpr modint61(ll x) : val(((x %= static_cast<ll>(mod)) < 0) ? (x + static_cast<ll>(mod)) : x) {}
  static constexpr u64 get_mod() { return mod; }

  modint61 &operator+=(const modint61 &a) {
    val = ((val += a.val) >= mod) ? (val - mod) : val;
    return *this;
  }
  modint61 &operator-=(const modint61 &a) {
    val = ((val -= a.val) >= mod) ? (val + mod) : val;
    return *this;
  }
  modint61 &operator*=(const modint61 &a) {
    const unsigned __int128 y = static_cast<unsigned __int128>(val) * a.val;
    val = (y >> 61) + (y & mod);
    val = (val >= mod) ? (val - mod) : val;
    return *this;
  }
  modint61 operator-() const { return modint61(val ? mod - val : u64(0)); }
  modint61 &operator/=(const modint61 &a) { return (*this *= a.inverse()); }
  modint61 operator+(const modint61 &p) const { return modint61(*this) += p; }
  modint61 operator-(const modint61 &p) const { return modint61(*this) -= p; }
  modint61 operator*(const modint61 &p) const { return modint61(*this) *= p; }
  modint61 operator/(const modint61 &p) const { return modint61(*this) /= p; }
  bool operator<(const modint61 &other) const { return val < other.val; }
  bool operator==(const modint61 &p) const { return val == p.val; }
  bool operator!=(const modint61 &p) const { return val != p.val; }
  modint61 inverse() const {
    ll a = val, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b), swap(u -= t * v, v);
    }
    return modint61(u);
  }
  modint61 pow(ll n) const {
    assert(n >= 0);
    modint61 ret(1), mul(val);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul, n >>= 1;
    }
    return ret;
  }
};

#ifdef FASTIO
void rd(modint61 &x) {
  fastio::rd(x.val);
  assert(0 <= x.val && x.val < modint61::mod);
}

void wt(modint61 x) { fastio::wt(x.val); }
#endif

Back to top page