Doubling

クラス · ダブリング (doubling)

template <int L = 20, doubling_monoid M = void>
struct Doubling;

概要

ダブリング

各要素の「次の遷移先」を $2^k$ ステップ分前計算し、jump で任意ステップ数のジャンプを $O(\log k)$ で行う。モノイド M を与えると遷移に沿った値を集約し、jump が {遷移先, 集約値} を返す。

テンプレートパラメータ

名前	説明
`L`	前計算する段数（$2^L$ ステップまで扱える）。
`M`	モノイド型（`value_type` / `id()` / `op()` を持つ）。`void` なら遷移先のみを扱い、`jump` は `int` を返す（`max_step` は提供しない）。

備考

void は内部で std::monostate に正規化し、本体を 1 つに保つ。集約表はモノイドがあるときだけ実体を持つ。

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 遷移先のみを前計算する (2) 遷移先と各ステップの集約値を前計算する	頂点数を $n$ として $O(Ln)$

メンバ関数

名前	説明	計算量
`jump`	vからstepステップ後の遷移先と必要なら集約値を返す	$O(L)=O(\log \mathrm{step})$
`max_step`	(1) check(M::op(init, accumulated)) が真である最大ステップ数を返す (2) 単位元から開始してcheckが真である最大ステップ数を返す	$O(L)$

メンバの詳細

(constructor)

// (1)
explicit Doubling(const std::vector<int> &to) requires(!has_monoid);

// (2)
template <class U>
requires has_monoid
Doubling(const std::vector<int> &to, const std::vector<U> &values);

(1) 遷移先のみを前計算する

パラメータ to: 各頂点から1ステップ後の遷移先
計算量: 頂点数を $n$ として $O(Ln)$

(2) 遷移先と各ステップの集約値を前計算する

パラメータ to: 各頂点から1ステップ後の遷移先
パラメータ values: 各頂点から進む1ステップに対応する値
計算量: 頂点数を $n$ として $O(Ln)$

max_step

// (1)
template <class F>
requires has_monoid
std::uint64_t max_step(int v, stored_value init, F check) const;

// (2)
template <class F>
requires has_monoid
std::uint64_t max_step(int v, F check) const;

(1) check(M::op(init, accumulated)) が真である最大ステップ数を返す

check は単調 (真→偽に一度だけ変化) を仮定する

計算量: $O(L)$

(2) 単位元から開始してcheckが真である最大ステップ数を返す