高速 zeta 変換

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /fast-zeta-transform#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /fast-zeta-transform#noredirect を利用してください。
name
高速 zeta 変換
short description
高速 zeta 変換とは、$n$ 要素の集合 $X$ の部分集合から可換 monoid $M$ への関数 $f : \mathcal{P}(X) \to M$ が与えられたとき、関数 $g(s) = \sum _ {s \subseteq T} f(T)$ の全体を $O(n 2^n)$ で求めるアルゴリズムである。累積和の $n$ 次元への一般化と理解できる。
input
$n$ 要素の集合 $X$ の部分集合から可換 monoid $M$ への関数 $f : \mathcal{P}(X) \to M$ のグラフ
output
関数 $g(s) = \sum _ {s \subseteq T} f(T)$ のグラフ
time complexity
$O(n 2^n)$