高速ゼータ変換 - とどの日記

id:iwiwiさんの高速ゼータ変換に関する記事
http://topcoder.g.hatena.ne.jp/iwiwi/20120422/1335065228
が恥ずかしながら分からなかったので，自分なりに解釈した．

やりたいこと

集合に関する関数 $f(S)$ があり，全集合 $S$ について，
$g(S) := \sum_{S \subseteq T} f(T)$
を求めたい．

コード

for(int i=0; i<n; i++)
    for(int s=0; s<1<<n; s++)
        if ((s>>i&1)==0)
            a[s]+=a[s|(1<<i)];

ただし，a[s]には予め $f(S)$ が入っている．

実行の様子

n=3としてi=0の時の処理が終わった後のaの中身は以下のようになっている．
000：000, 001
001：001
010：010, 011
011：011
100：100, 101
101：101
110：110, 111
111：111
左はインデックス集合，右は（その関数値の）和を取られた集合を表す．赤い集合はこのステップで初めて足されたもの．
各集合について，一番右端のビット「以外」を固定した集合の中で包含関係（右が左を包む）が成り立つもの全ての和をとっている．右端のビットが1の集合についてはa[s]+=a[s|(1<010, 011
001：001, 011
010：010, 011
011：011
100：100, 101, 110, 111
101：101, 111
110：110, 111
111：111
今度は，一番右端とその左隣のビット以外，即ち一番左端のビットのみを固定した時に包含関係が成り立つ全集合の和をとっている．

最後には以下のようになる．
000：000, 001, 010, 011, 100, 101, 110, 111
001：001, 011, 101, 111
010：010, 011, 110, 111
011：011, 111
100：100, 101, 110, 111
101：101, 111
110：110, 111
111：111
これで，左の集合を包含する全集合（の関数値）の和がとれる．

$S$ と $T$ の関係を逆にした場合 $g(S) := \sum_{T \subseteq S} f(T)$ は，

コード

for(int i=0; i<n; i++)
    for(int s=0; s<1<<n; s++)
        if ((s>>i&1)==1)
            a[s]+=a[s^(1<<i)];

で良い．