ZetaMobius 名前空間

ゼータ変換・メビウス変換 [詳解]

関数
template<typename Monoid>
vector< typename Monoid::Type >	SubsetZeta (vector< typename Monoid::Type > v)
	高速ゼータ変換（下位集合）
template<typename Monoid>
vector< typename Monoid::Type >	SupersetZeta (vector< typename Monoid::Type > v)
	高速ゼータ変換（上位集合）
template<typename Abel>
vector< typename Abel::Type >	SubsetMobius (vector< typename Abel::Type > v)
	高速メビウス変換（下位集合）
template<typename Abel>
vector< typename Abel::Type >	SupersetMobius (vector< typename Abel::Type > v)
	高速メビウス変換（上位集合）

詳解

ゼータ変換・メビウス変換

関数詳解

SubsetZeta()

template<typename Monoid>

vector< typename Monoid::Type > ZetaMobius::SubsetZeta

(

vector< typename Monoid::Type >

v

)

高速ゼータ変換（下位集合）

v'[s] = Σ_{t⊆s} v[t] なる v' を返す

覚え書き

|v| = 2^N として O(N 2^N)

zeta_mobius.hpp の 9 行目に定義があります。

SupersetZeta()

template<typename Monoid>

vector< typename Monoid::Type > ZetaMobius::SupersetZeta

(

vector< typename Monoid::Type >

v

)

高速ゼータ変換（上位集合）

v'[s] = Σ_{t⊇s} v[t] なる v' を返す

覚え書き

|v| = 2^N として O(N 2^N)

zeta_mobius.hpp の 21 行目に定義があります。

SubsetMobius()

template<typename Abel>

vector< typename Abel::Type > ZetaMobius::SubsetMobius

(

vector< typename Abel::Type >

v

)

高速メビウス変換（下位集合）

v[s] = Σ_{t⊆s} v'[t] なる v' を返す

覚え書き

逆変換が必要なので、v は可換群の元である必要がある

|v| = 2^N として O(N 2^N)

zeta_mobius.hpp の 34 行目に定義があります。

SupersetMobius()

template<typename Abel>

vector< typename Abel::Type > ZetaMobius::SupersetMobius

(

vector< typename Abel::Type >

v

)

高速メビウス変換（上位集合）

v[s] = Σ_{t⊇s} v'[t] なる v' を返す

覚え書き

逆変換が必要なので、v は可換群の元である必要がある

|v| = 2^N として O(N 2^N)

zeta_mobius.hpp の 47 行目に定義があります。