DoublingFold< Monoid, Log > 構造体テンプレート

ダブリング（モノイド合成） [詳解]

#include "doubling_fold.hpp"

公開型
using	Type = typename Monoid::Type

公開メンバ関数
	DoublingFold ()=default
	DoublingFold (const vector< int > &p, const vector< Type > &v)
	コンストラクタ
Type	fold (int start, ll k)
	モノイド積
int	next (int start, ll k)
	頂点 start から k 回遷移した先の頂点を返す

詳解

template<typename Monoid, int Log>
struct DoublingFold< Monoid, Log >

ダブリング（モノイド合成）

テンプレート引数

Monoid	合成するモノイド
Log	ダブリングの深さ

doubling_fold.hpp の 7 行目に定義があります。

型定義メンバ詳解

Type

template<typename Monoid, int Log>

using DoublingFold< Monoid, Log >::Type = typename Monoid::Type

doubling_fold.hpp の 8 行目に定義があります。

構築子と解体子

DoublingFold() [1/2]

template<typename Monoid, int Log>

DoublingFold< Monoid, Log >::DoublingFold ( )

default

DoublingFold() [2/2]

template<typename Monoid, int Log>

DoublingFold< Monoid, Log >::DoublingFold ( const vector< int > & p, const vector< Type > & v )

inline

コンストラクタ

引数

p	各頂点の遷移先
v	各頂点の値

覚え書き

O(N Log)

doubling_fold.hpp の 15 行目に定義があります。

関数詳解

fold()

template<typename Monoid, int Log>

Type DoublingFold< Monoid, Log >::fold ( int start, ll k )

inline

モノイド積

頂点 start から k 回遷移したときのモノイド積を返す

覚え書き

O(Log)

doubling_fold.hpp の 29 行目に定義があります。

next()

template<typename Monoid, int Log>

int DoublingFold< Monoid, Log >::next ( int start, ll k )

inline

頂点 start から k 回遷移した先の頂点を返す

覚え書き

O(Log)

doubling_fold.hpp の 40 行目に定義があります。

---

この構造体詳解は次のファイルから抽出されました:

• algorithm/doubling_fold.hpp