高速ゼータ変換

高速ゼータ変換はある要素群を取り出した時に、
その群の組み合わせをすべて試して要素の点数の和を返すことができる。
こまかく説明すると以下のようになる。

N個の要素がある。
N個の要素のうちいくつかが含まれるとPi点という点数が存在する。
N=kであればPiは2^k個存在する。
N個の要素からいくつか取り出しグループAとする。
次にグループAからいくつか要素を取り出しグループBとする。
グループAに対してありうるグループBの点数の和を求める。
この計算はまずグループAを求めるのに2^N回。
さらにグループAからグループBを求めるのに2^N回の探索が必要。
よって、全体ではO(4^N)の計算量となる。
高速ゼータ変換はこの操作をO(N2^N)まで高速化できる。
O(4^N)のときN=10程度でないと2秒以内に処理が終わらないが、
O(N2^N)はN=20でも2秒以内に処理を終えることができる。

int z[1<<20];

for(int s = 0; s < (1 << n); s++){
  z[s] = P[s]; // 点数を設定
}

// 高速ゼータ変換
for(int k = 0; k < n; k++) {
  for(int s = 0; s < (1 << n); s++) {
    if((s >> k) & 1) {
      z[s] += z[s ^ (1 << k)];
    }
  }
}