Hatena::ブログ(Diary)

とどの日記

2012-06-14

高速ゼータ変換

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<<i)]は実行されない.

i=1の処理が終わると次のようになる.

000:000, 001, 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

これで,左の集合を包含する全集合(の関数値)の和がとれる.

STの関係を逆にした場合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)];

で良い.

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証