高速ゼータ変換(メビウス逆変換)

keyword:zeta, mebius

カートに追加

overview

ゼータ変換は,集合関数f(2^S)=Nを g(X) = sum{X⊆Y}(f(Y)) に変換する. プログラミング上では,f,gは多くの場合, 関数ではなく配列として表現される. 高速ゼータ変換は,愚直に計算すると4^Nになるところ, N2^Nで計算するシンプルなDPである.

usage

vector zeta_transform(int n, vector func);
vector mebius_transform(int n, vector func)
; 集合はビットで表現.
; func.size() >= (1 << n) を満たす.

verified

unverified!!!

references

https://topcoder.g.hatena.ne.jp/iwiwi/20120422/1335065228
https://naoyat.hatenablog.jp/entry/zeta-moebius
講義資料

require

code