Sum over Subsets DP (SOS DP) メモ

いわゆる高速ゼータ変換

集合Sに対応する値をa_Sと表記する

 

下位集合をまとめるタイプ

dp[i][mask]:=maskの部分集合であって、i<=xをみたすようなx bit目はmaskと一致するような部分集合についての値(maskごとの累積和)

 

dp[0][mask]=a_mask として、

i bit目が立っている時、dp[i][mask]=f (dp[i-1][mask],dp[i-1][mask - (1<<i))] )

i bit目が立っていない時、dp[i][mask]=dp[[i-1]mask]

(i次元累積和と同じ)

 

dp[bit数][mask]=maskの全ての部分集合Tに対して、a_Tに演算fを行った結果

 

全部分集合についての値が知りたいだけの場合、一つ目の添え字を使い回せる

 

 

上位集合をまとめるタイプ

DPの定義式は下位集合の場合と同じ

 

i bit目が立っている時、dp[i][mask]=dp[[i-1]mask]

i bit目が立っていない時、dp[i][mask]=f (dp[i-1][mask],dp[i-1][mask + (1<<i))] )

 

dp[bit数][mask]=maskを部分集合として含むような全ての集合Sに対して、a_Sに演算fを行った結果

 

 

fは結合律・交換律が成り立つ演算である必要がある

・ある部分集合について処理を行った結果をそのまま演算する→最後にまとめて演算をする必要がないことが必要

・演算順序は一定(iが小さい方から処理される)→計算結果が部分集合の値を演算する順番によらないことが必要

 

 

 

 

高速ゼータ変換の逆変換は高速メビウス変換と呼ばれる(いわゆる包除原理)