いわゆる高速ゼータ変換
集合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が小さい方から処理される）→計算結果が部分集合の値を演算する順番によらないことが必要
高速ゼータ変換の逆変換は高速メビウス変換と呼ばれる（いわゆる包除原理)