Rolling hash (tools/rolling_hash.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-02-10 01:30:13+09:00
• Include: #include "tools/rolling_hash.hpp"

It calculates hash values for any subsequences of a given sequence.

License

• CC0

Author

• anqooqie

Constructor

template <typename InputIterator>
rolling_hash hash(InputIterator begin, InputIterator end);

It calculates hash values for any subsequences of a given sequence.

Constraints

• None of the elements in a given sequence are $0$.

Time Complexity

• $O(n)$ where $n$ is end $-$ begin

pow_base

tools::modint_for_rolling_hash hash.pow_base(std::size_t i);

It returns $b^{i} \pmod{2^{61} - 1}$ where $b$ is the integer randomly determined immediately after startup of the program.

Constraints

• None

Time Complexity

• (first call): $O(i)$
• (second call or later): $O(i - i^\ast)$ where $i^\ast$ is the largest $i$ in the pow_base calls so far

slice

tools::modint_for_rolling_hash hash.slice(std::size_t l, std::size_t r);

It returns $\sum_{i = l}^{r - 1} s_i b^{r - 1 - i} \pmod{2^{61} - 1}$ where $s_i$ is the $i$-th element of the given sequence.

Constraints

• $0 \leq l \leq r \leq n$

Time Complexity

• $O(1)$

Depends on

• std::abs(x) extended for my library (tools/abs.hpp)
• $\left\lceil \frac{x}{y} \right\rceil$ (tools/ceil.hpp)
• tools/detail/rolling_hash.hpp
• Extended Euclidean algorithm (tools/extgcd.hpp)
• Floyd's cycle-finding algorithm (tools/find_cycle.hpp)
• $\left\lfloor \frac{x}{y} \right\rfloor$ (tools/floor.hpp)
• std::gcd(m, n) extended for my library (tools/gcd.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• Check whether T is a monoid (tools/is_monoid.hpp)
• std::is_unsigned extended for tools::int128_t and tools::uint128_t (tools/is_unsigned.hpp)
• Minimum non-negative reminder (tools/mod.hpp)
• Typical monoids (tools/monoid.hpp)
• The number of nanoseconds that have elapsed since epoch (tools/now.hpp)
• $b^n$ under a given monoid, and std::pow(b, n) extended for my library (tools/pow.hpp)
• Cache for $b^n \pmod{M}$ (tools/pow_mod_cache.hpp)
• $x^2$ under a given monoid (tools/square.hpp)

Verified with

• tests/rolling_hash.test.cpp

Code

#ifndef TOOLS_ROLLING_HASH_HPP
#define TOOLS_ROLLING_HASH_HPP

#include "tools/detail/rolling_hash.hpp"

#endif

#line 1 "tools/rolling_hash.hpp"



#line 1 "tools/detail/rolling_hash.hpp"



#include <cstdint>
#include <cassert>
#include <tuple>
#include <vector>
#line 1 "tools/pow.hpp"



#include <type_traits>
#line 6 "tools/pow.hpp"
#include <cmath>
#line 1 "tools/monoid.hpp"



#line 5 "tools/monoid.hpp"
#include <algorithm>
#include <limits>
#line 1 "tools/gcd.hpp"



#line 5 "tools/gcd.hpp"
#include <numeric>

namespace tools {
  template <typename M, typename N>
  constexpr ::std::common_type_t<M, N> gcd(const M m, const N n) {
    return ::std::gcd(m, n);
  }
}


#line 9 "tools/monoid.hpp"

namespace tools {
  namespace monoid {
    template <typename M, M ...dummy>
    struct max;

    template <typename M>
    struct max<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::max(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::min();
        } else {
          return -::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct max<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(E <= lhs);
        assert(E <= rhs);
        return ::std::max(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M, M ...dummy>
    struct min;

    template <typename M>
    struct min<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::min(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::max();
        } else {
          return ::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct min<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(lhs <= E);
        assert(rhs <= E);
        return ::std::min(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M>
    struct multiplies {
    private:
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return lhs * rhs;
      }
      static T e() {
        return T(1);
      }
    };

    template <>
    struct multiplies<bool> {
      using T = bool;
      static T op(const bool lhs, const bool rhs) {
        return lhs && rhs;
      }
      static T e() {
        return true;
      }
    };

    template <typename M>
    struct gcd {
    private:
      static_assert(!::std::is_arithmetic_v<M> || (::std::is_integral_v<M> && !::std::is_same_v<M, bool>), "If M is a built-in arithmetic type, it must be integral except for bool.");
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return ::tools::gcd(lhs, rhs);
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M, M E>
    struct update {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return lhs == E ? rhs : lhs;
      }
      static T e() {
        return E;
      }
    };
  }
}


#line 1 "tools/square.hpp"



#line 1 "tools/is_monoid.hpp"



#line 5 "tools/is_monoid.hpp"
#include <utility>

namespace tools {

  template <typename M, typename = void>
  struct is_monoid : ::std::false_type {};

  template <typename M>
  struct is_monoid<M, ::std::enable_if_t<
    ::std::is_same_v<typename M::T, decltype(M::op(::std::declval<typename M::T>(), ::std::declval<typename M::T>()))> &&
    ::std::is_same_v<typename M::T, decltype(M::e())>
  , void>> : ::std::true_type {};

  template <typename M>
  inline constexpr bool is_monoid_v = ::tools::is_monoid<M>::value;
}


#line 6 "tools/square.hpp"

namespace tools {

  template <typename M>
  ::std::enable_if_t<::tools::is_monoid_v<M>, typename M::T> square(const typename M::T& x) {
    return M::op(x, x);
  }

  template <typename T>
  ::std::enable_if_t<!::tools::is_monoid_v<T>, T> square(const T& x) {
    return x * x;
  }
}


#line 9 "tools/pow.hpp"

namespace tools {

  template <typename M, typename E>
  ::std::enable_if_t<::std::is_integral_v<E>, typename M::T> pow(const typename M::T& base, const E exponent) {
    assert(exponent >= 0);
    return exponent == 0
      ? M::e()
      : exponent % 2 == 0
        ? ::tools::square<M>(::tools::pow<M>(base, exponent / 2))
        : M::op(::tools::pow<M>(base, exponent - 1), base);
  }

  template <typename T, typename E>
  ::std::enable_if_t<::std::is_integral_v<E>, T> pow(const T& base, const E exponent) {
    assert(exponent >= 0);
    return ::tools::pow<::tools::monoid::multiplies<T>>(base, exponent);
  }

  template <typename T, typename E>
  auto pow(const T base, const E exponent) -> ::std::enable_if_t<!::std::is_integral_v<E>, decltype(::std::pow(base, exponent))> {
    return ::std::pow(base, exponent);
  }
}


#line 1 "tools/extgcd.hpp"



#line 1 "tools/abs.hpp"



namespace tools {
  constexpr float abs(const float x) {
    return x < 0 ? -x : x;
  }
  constexpr double abs(const double x) {
    return x < 0 ? -x : x;
  }
  constexpr long double abs(const long double x) {
    return x < 0 ? -x : x;
  }
  constexpr int abs(const int x) {
    return x < 0 ? -x : x;
  }
  constexpr long abs(const long x) {
    return x < 0 ? -x : x;
  }
  constexpr long long abs(const long long x) {
    return x < 0 ? -x : x;
  }
  constexpr unsigned int abs(const unsigned int x) {
    return x;
  }
  constexpr unsigned long abs(const unsigned long x) {
    return x;
  }
  constexpr unsigned long long abs(const unsigned long long x) {
    return x;
  }
}


#line 9 "tools/extgcd.hpp"

namespace tools {

  template <typename T>
  ::std::tuple<T, T, T> extgcd(T prev_r, T r) {
    const bool prev_r_is_neg = prev_r < T(0);
    const bool r_is_neg = r < T(0);

    if (prev_r_is_neg) prev_r = -prev_r;
    if (r_is_neg) r = -r;

    #ifndef NDEBUG
    const T a = prev_r;
    const T b = r;
    #endif

    T prev_s(1);
    T prev_t(0);
    T s(0);
    T t(1);
    while (r != T(0)) {
      const T q = prev_r / r;
      ::std::tie(prev_r, r) = ::std::make_pair(r, prev_r - q * r);
      ::std::tie(prev_s, s) = ::std::make_pair(s, prev_s - q * s);
      ::std::tie(prev_t, t) = ::std::make_pair(t, prev_t - q * t);
    }

    if (prev_r_is_neg) prev_s = -prev_s;
    if (r_is_neg) prev_t = -prev_t;

    assert(::tools::abs(prev_s) <= ::std::max(b / prev_r / T(2), T(1)));
    assert(::tools::abs(prev_t) <= ::std::max(a / prev_r / T(2), T(1)));
    return ::std::make_tuple(prev_s, prev_t, prev_r);
  }
}


#line 1 "tools/pow_mod_cache.hpp"



#line 5 "tools/pow_mod_cache.hpp"
#include <optional>
#line 8 "tools/pow_mod_cache.hpp"
#include <cstddef>
#line 10 "tools/pow_mod_cache.hpp"
#include <iterator>
#line 1 "tools/find_cycle.hpp"



#line 5 "tools/find_cycle.hpp"

namespace tools {

  template <typename T, typename F>
  ::std::pair<long long, long long> find_cycle(const T& seed, const F& f) {
    auto i = 1LL;
    auto j = 2LL;
    T x = f(seed);
    T y = f(f(seed));
    for (; x != y; ++i, j += 2, x = f(x), y = f(f(y)));

    i = 0;
    x = seed;
    for (; x != y; ++i, ++j, x = f(x), y = f(y));

    const auto head = i;

    ++i;
    j = i + 1;
    x = f(x);
    y = f(f(y));
    for (; x != y; ++i, j += 2, x = f(x), y = f(f(y)));

    const auto cycle = j - i;

    return ::std::make_pair(head, cycle);
  }
}


#line 1 "tools/mod.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 7 "tools/mod.hpp"

namespace tools {

  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> mod(const M a, const N b) noexcept {
    assert(b != 0);

    using UM = ::std::make_unsigned_t<M>;
    using UN = ::std::make_unsigned_t<N>;
    const UM ua = a >= 0 ? a : static_cast<UM>(-(a + 1)) + 1;
    const UN ub = b >= 0 ? b : static_cast<UN>(-(b + 1)) + 1;
    auto r = ua % ub;
    if (a < 0 && r > 0) {
      r = ub - r;
    }
    return r;
  }
}


#line 1 "tools/floor.hpp"



#line 7 "tools/floor.hpp"

namespace tools {

  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> floor(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x >= 0) {
        return x / y;
      } else {
        return (x + 1) / y - 1;
      }
    } else {
      if (x > 0) {
        return (x - 1) / y - 1;
      } else {
        return x / y;
      }
    }
  }
}


#line 1 "tools/ceil.hpp"



#line 1 "tools/is_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

namespace tools {
  template <typename T>
  struct is_unsigned : ::std::is_unsigned<T> {};

  template <typename T>
  inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}


#line 8 "tools/ceil.hpp"

namespace tools {
  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> ceil(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x > 0) {
        return (x - 1) / y + 1;
      } else {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      }
    } else {
      if (x >= 0) {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      } else {
        return (x + 1) / y + 1;
      }
    }
  }
}


#line 16 "tools/pow_mod_cache.hpp"

namespace tools {

  template <class M>
  class pow_mod_cache {
    ::std::vector<M> m_pow;
    ::std::vector<M> m_cumsum;
    ::std::vector<M> m_inv_pow;
    ::std::vector<M> m_inv_cumsum;
    ::std::optional<::std::pair<long long, long long>> m_period;

  public:
    pow_mod_cache() = default;
    explicit pow_mod_cache(const M base) : m_pow({M(1), base}), m_cumsum({M::raw(0)}), m_inv_pow({M(1)}), m_inv_cumsum({M::raw(0)}) {
      if (base == M(-1)) {
        if (M::mod() > 2) {
          this->m_period = ::std::make_pair(0LL, 2LL);
        } else {
          this->m_period = ::std::make_pair(0LL, 1LL);
          this->m_pow.resize(1);
        }
        this->m_inv_pow.clear();
        this->m_inv_cumsum.clear();
      }
    }
    template <typename Z, ::std::enable_if_t<::std::is_integral_v<Z>, ::std::nullptr_t> = nullptr>
    explicit pow_mod_cache(const Z base) : pow_mod_cache(M(base)) {
    }

    M operator[](const long long n) {
      if (!this->m_period) {
        if (::std::max<long long>(::std::ssize(this->m_pow) - 1, n) - ::std::min<long long>(n, -(::std::ssize(this->m_inv_pow) - 1)) + 1 < M::mod() - 1) {
          if (n >= 0) {
            const long long size = ::std::ssize(this->m_pow);
            this->m_pow.resize(::std::max(size, n + 1));
            for (long long i = size; i < ::std::ssize(this->m_pow); ++i) {
              this->m_pow[i] = this->m_pow[i - 1] * this->m_pow[1];
            }
            return this->m_pow[n];
          } else {
            if (this->m_inv_pow.size() == 1) {
              this->m_inv_pow.push_back(this->m_pow[1].inv());
            }
            const long long size = ::std::ssize(this->m_inv_pow);
            this->m_inv_pow.resize(::std::max(size, -n + 1));
            for (long long i = size; i < ::std::ssize(this->m_inv_pow); ++i) {
              this->m_inv_pow[i] = this->m_inv_pow[i - 1] * this->m_inv_pow[1];
            }
            return this->m_inv_pow[-n];
          }
        }

        this->m_period = ::tools::find_cycle(this->m_pow[0], [&](const M& prev) { return prev * this->m_pow[1]; });
        const long long size = ::std::ssize(this->m_pow);
        this->m_pow.resize(this->m_period->first + this->m_period->second);
        for (long long i = size; i < ::std::ssize(this->m_pow); ++i) {
          this->m_pow[i] = this->m_pow[i - 1] * this->m_pow[1];
        }
        this->m_inv_pow.clear();
        this->m_inv_cumsum.clear();
      }

      if (this->m_period->first == 0) {
        return this->m_pow[::tools::mod(n, this->m_period->second)];
      } else {
        assert(n >= 0);
        if (n < this->m_period->first + this->m_period->second) {
          return this->m_pow[n];
        } else {
          return this->m_pow[(n - this->m_period->first) % this->m_period->second + this->m_period->first];
        }
      }
    }

    M sum(const long long l, const long long r) {
      if (l >= r) return M::raw(0);

      (*this)[r - 1];
      (*this)[l];

      {
        const long long size = ::std::ssize(this->m_cumsum);
        this->m_cumsum.resize(this->m_pow.size() + 1);
        for (long long i = size; i < ::std::ssize(this->m_cumsum); ++i) {
          this->m_cumsum[i] = this->m_cumsum[i - 1] + this->m_pow[i - 1];
        }
      }

      if (!this->m_period) {
        const long long size = ::std::ssize(this->m_inv_cumsum);
        this->m_inv_cumsum.resize(this->m_inv_pow.size() + 1);
        for (long long i = size; i < ::std::ssize(this->m_inv_cumsum); ++i) {
          this->m_inv_cumsum[i] = this->m_inv_cumsum[i - 1] + this->m_pow[i - 1];
        }

        if (l >= 0) {
          return this->m_cumsum[r] - this->m_cumsum[l];
        } else if (r <= 0) {
          return this->m_inv_cumsum[-l] - this->m_inv_cumsum[-r];
        } else {
          return (this->m_inv_cumsum[-l] - this->m_inv_cumsum[1]) + (this->m_cumsum[r] - this->m_cumsum[0]);
        }
      }

      static const auto cumsum = [&](const long long ll, const long long rr) {
        return this->m_cumsum[rr] - this->m_cumsum[ll];
      };

      if (l >= 0) {
        static const auto f = [&](const long long x) {
          if (x <= this->m_period->first + this->m_period->second) {
            return cumsum(0, x);
          } else {
            return cumsum(0, this->m_period->first) +
              cumsum(this->m_period->first, this->m_period->first + this->m_period->second) * ((x - this->m_period->first) / this->m_period->second) +
              cumsum(this->m_period->first, (x - this->m_period->first) % this->m_period->second + this->m_period->first);
          }
        };
        return f(r) - f(l);
      } else {
        const auto& n = this->m_period->second;
        return cumsum(::tools::mod(l, n), n) + cumsum(0, ::tools::mod(r, n)) + cumsum(0, n) * M(::tools::floor(r, n) - ::tools::ceil(l, n));
      }
    }
  };
}


#line 1 "tools/now.hpp"



#include <chrono>

namespace tools {
  inline long long now() {
    return ::std::chrono::duration_cast<::std::chrono::nanoseconds>(::std::chrono::high_resolution_clock::now().time_since_epoch()).count();
  }
}


#line 12 "tools/detail/rolling_hash.hpp"

namespace tools {
  class rolling_hash;

  class modint_for_rolling_hash {
  private:
    static constexpr ::std::uint64_t MASK30 = (::std::uint64_t(1) << 30) - 1;
    static constexpr ::std::uint64_t MASK31 = (::std::uint64_t(1) << 31) - 1;
    static constexpr ::std::uint64_t MOD = (::std::uint64_t(1) << 61) - 1;
    static constexpr ::std::uint64_t MASK61 = MOD;
    static constexpr ::std::uint64_t POSITIVIZER = MOD * 4;

    ::std::uint64_t m_val;

    modint_for_rolling_hash(const ::std::uint64_t x, int) : m_val(x) {
    }

    static ::std::uint64_t mul(const ::std::uint64_t a, const ::std::uint64_t b) {
      assert(a < MOD);
      assert(b < MOD);
      const ::std::uint64_t au = a >> 31;
      const ::std::uint64_t ad = a & MASK31;
      const ::std::uint64_t bu = b >> 31;
      const ::std::uint64_t bd = b & MASK31;
      const ::std::uint64_t mid = ad * bu + au * bd;
      const ::std::uint64_t midu = mid >> 30;
      const ::std::uint64_t midd = mid & MASK30;
      return au * bu * 2 + midu + (midd << 31) + ad * bd;
    }
    static ::std::uint64_t calc_mod(const ::std::uint64_t x) {
      const ::std::uint64_t xu = x >> 61;
      const ::std::uint64_t xd = x & MASK61;
      ::std::uint64_t res = xu + xd;
      if (res >= MOD) res -= MOD;
      return res;
    }

  public:
    modint_for_rolling_hash() = default;
    modint_for_rolling_hash(const ::tools::modint_for_rolling_hash&) = default;
    modint_for_rolling_hash(::tools::modint_for_rolling_hash&&) = default;
    ~modint_for_rolling_hash() = default;
    ::tools::modint_for_rolling_hash& operator=(const ::tools::modint_for_rolling_hash&) = default;
    ::tools::modint_for_rolling_hash& operator=(::tools::modint_for_rolling_hash&&) = default;

    explicit modint_for_rolling_hash(const ::std::uint64_t x) : m_val(calc_mod(x)) {
    }

    ::tools::modint_for_rolling_hash pow(const long long n) const {
      return ::tools::pow(*this, n);
    }
    ::tools::modint_for_rolling_hash inv() const {
      assert(this->m_val != 0);
      return ::tools::modint_for_rolling_hash(::std::get<0>(::tools::extgcd(this->m_val, MOD)));
    }

    ::tools::modint_for_rolling_hash operator+() const {
      return *this;
    }
    ::tools::modint_for_rolling_hash operator-() const {
      return ::tools::modint_for_rolling_hash(POSITIVIZER - this->m_val);
    }
    friend ::tools::modint_for_rolling_hash operator+(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return ::tools::modint_for_rolling_hash(lhs.m_val + rhs.m_val);
    }
    ::tools::modint_for_rolling_hash& operator+=(const ::tools::modint_for_rolling_hash& other) {
      this->m_val = calc_mod(this->m_val + other.m_val);
      return *this;
    }
    friend ::tools::modint_for_rolling_hash operator-(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return ::tools::modint_for_rolling_hash(lhs.m_val + POSITIVIZER - rhs.m_val);
    }
    ::tools::modint_for_rolling_hash& operator-=(const ::tools::modint_for_rolling_hash& other) {
      this->m_val = calc_mod(this->m_val + POSITIVIZER - other.m_val);
      return *this;
    }
    friend ::tools::modint_for_rolling_hash operator*(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return ::tools::modint_for_rolling_hash(mul(lhs.m_val, rhs.m_val));
    }
    ::tools::modint_for_rolling_hash& operator*=(const ::tools::modint_for_rolling_hash& other) {
      this->m_val = calc_mod(mul(this->m_val, other.m_val));
      return *this;
    }
    friend ::tools::modint_for_rolling_hash operator/(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return ::tools::modint_for_rolling_hash(mul(lhs.m_val, rhs.inv().m_val));
    }
    ::tools::modint_for_rolling_hash& operator/=(const ::tools::modint_for_rolling_hash& other) {
      this->m_val = calc_mod(mul(this->m_val, other.inv().m_val));
      return *this;
    }
    ::tools::modint_for_rolling_hash& operator++() {
      this->m_val = calc_mod(this->m_val + 1);
      return *this;
    }
    ::tools::modint_for_rolling_hash operator++(int) {
      const auto result = *this;
      ++(*this);
      return result;
    }
    ::tools::modint_for_rolling_hash& operator--() {
      this->m_val = calc_mod(this->m_val + POSITIVIZER - 1);
      return *this;
    }
    ::tools::modint_for_rolling_hash operator--(int) {
      const auto result = *this;
      --(*this);
      return result;
    }

    friend bool operator==(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return lhs.m_val == rhs.m_val;
    }
    friend bool operator!=(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return lhs.m_val != rhs.m_val;
    }

    long long val() const {
      return this->m_val;
    }

    static ::tools::modint_for_rolling_hash raw(const ::std::uint64_t x) {
      return ::tools::modint_for_rolling_hash(x, 0);
    }
    static long long mod() {
      return MOD;
    }

    friend ::tools::rolling_hash;
  };

  class rolling_hash {
  private:
    using mint = ::tools::modint_for_rolling_hash;
    inline static ::tools::pow_mod_cache<mint> m_pow_base = ::tools::pow_mod_cache<mint>(::tools::now());
    ::std::vector<mint> m_hash;

  public:
    rolling_hash() = default;
    rolling_hash(const ::tools::rolling_hash&) = default;
    rolling_hash(::tools::rolling_hash&&) = default;
    ~rolling_hash() = default;
    ::tools::rolling_hash& operator=(const ::tools::rolling_hash&) = default;
    ::tools::rolling_hash& operator=(::tools::rolling_hash&&) = default;

    template <typename InputIterator>
    rolling_hash(InputIterator begin, InputIterator end) {
      this->m_hash.push_back(mint::raw(0));
      const auto base = m_pow_base[1].m_val;
      for (auto it = begin; it != end; ++it) {
        this->m_hash.emplace_back(mint::mul(this->m_hash.back().m_val, base) + *it);
      }
      m_pow_base[this->m_hash.size()];
    }

    mint pow_base(const ::std::size_t i) const {
      return m_pow_base[i];
    }

    mint slice(const ::std::size_t l, const ::std::size_t r) const {
      assert(l <= r && r <= this->m_hash.size());
      return mint(this->m_hash[r].m_val + mint::POSITIVIZER - mint::mul(this->m_hash[l].m_val, m_pow_base[r - l].m_val));
    }
  };
}


#line 5 "tools/rolling_hash.hpp"

Back to top page