HashInt

クラス · 法 $2^{61}-1$ 上の整数型

struct HashInt;

概要

法 $2^{61}-1$ 上の整数型

ローリングハッシュ向けに、加減乗除・比較・累乗・逆元を提供する。

計算量

加減乗算と比較は $O(1)$、pow(n) は $O(\log n)$、 inv() は $O(\log \mathrm{mod})$

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 0 で初期化する (2)、(3)、(4)、(5)、(6)、(7) 整数 `y` を法で正規化して初期化する	$O(1)$

メンバ関数

名前	説明	計算量
`long`	(1) 正規化済みの値を `unsigned long` へ変換する (2) 正規化済みの値を `long long` へ変換する (3) 正規化済みの値を `unsigned long long` へ変換する	$O(1)$
`inv`	乗法逆元を返す	$O(\log \mathrm{mod})$
`pow`	自身の `n` 乗を返す	$O(\log n)$
`pow_self`	自身を `n` 乗へ更新して返す	$O(\log n)$
`val`	$[0,2^{61}-1)$ に正規化された内部値を返す	$O(1)$

演算子

名前	説明	計算量
`operator+=`	`rhs` を加算する	$O(1)$
`operator-=`	`rhs` を減算する	$O(1)$
`operator*=`	`rhs` を乗算する	$O(1)$
`operator/=`	`rhs` で除算する	$O(\log \mathrm{mod})$
`operator++`	(1) 1 を加算して自身を返す (2) 1 を加算する前の値を返す	$O(1)$
`operator--`	(1) 1 を減算して自身を返す (2) 1 を減算する前の値を返す	$O(1)$
`operator-`	(1) 加法逆元を返す (2) `rhs` との差を返す	$O(1)$
`operator+`	`rhs` との和を返す	$O(1)$
`operator*`	`rhs` との積を返す	$O(1)$
`operator/`	`rhs` との商を返す	$O(\log \mathrm{mod})$
`operator==`	`rhs` と等しいなら true を返す	$O(1)$
`operator!=`	`rhs` と異なるなら true を返す	$O(1)$
`operator long`	正規化済みの値を `long` へ変換する	$O(1)$
`operator>>`	入力ストリームから整数を読み込む	$O(1)$
`operator<<`	正規化済みの値を出力ストリームへ書き込む	$O(1)$

静的メンバ関数

名前	説明	計算量
`get_mod`	法 $2^{61}-1$ を返す	$O(1)$

メンバの詳細

(constructor)

// (1)
constexpr HashInt() noexcept;

// (2)
constexpr HashInt(int y) noexcept;

// (3)
constexpr HashInt(unsigned int y) noexcept;

// (4)
constexpr HashInt(long y) noexcept;

// (5)
constexpr HashInt(unsigned long y) noexcept;

// (6)
constexpr HashInt(long long y) noexcept;

// (7)
constexpr HashInt(unsigned long long y) noexcept;

(1) 0 で初期化する

計算量: $O(1)$

(2)、(3)、(4)、(5)、(6)、(7) 整数 y を法で正規化して初期化する

計算量: $O(1)$

long

// (1)
constexpr explicit operator unsigned long() const noexcept;

// (2)
constexpr explicit operator long long() const noexcept;

// (3)
constexpr explicit operator unsigned long long() const noexcept;

(1) 正規化済みの値を unsigned long へ変換する

計算量: $O(1)$

(2) 正規化済みの値を long long へ変換する

計算量: $O(1)$

(3) 正規化済みの値を unsigned long long へ変換する

計算量: $O(1)$

operator++

// (1)
constexpr HashInt &operator++() noexcept;

// (2)
constexpr HashInt operator++(int) noexcept;

(1) 1 を加算して自身を返す

計算量: $O(1)$

(2) 1 を加算する前の値を返す

計算量: $O(1)$

operator–

// (1)
constexpr HashInt &operator--() noexcept;

// (2)
constexpr HashInt operator--(int) noexcept;

(1) 1 を減算して自身を返す

計算量: $O(1)$

(2) 1 を減算する前の値を返す

計算量: $O(1)$

operator-

// (1)
constexpr HashInt operator-() const noexcept;

// (2)
constexpr HashInt operator-(const HashInt &rhs) const noexcept;

(1) 加法逆元を返す

計算量: $O(1)$

(2) rhs との差を返す

計算量: $O(1)$