naoya_t@hatenablog

いわゆるチラシノウラであります

〈説明用メモ〉O(3^N)について本気出して考えてみた

Algorithms memo

n個ある何かの0個以上から成る集合Sをnビットの整数で表すことにする。
このとき、集合に含まれる要素がk個なら全部でkビット立っている 。
（__builtin_popcount(S) == k）

この集合Sの部分集合Tをすべて列挙しようとすると、空集合も含め2^k通りある。
集合Sとしてありうる全てのパターンについてこれを列挙することを考えると、
n個からk個選ぶ組み合わせが_nC_k通りで、そのそれぞれについて2^k通りの部分集合があるので全部で \displaystyle\sum_{k=0}^{n}{_nC_k\cdot2^k} 通りについて考えることになる。

ここで驚くべきことは、任意の非負整数nについて
$$ \sum_{k=0}^{n}{_nC_k\cdot2^k}=3^n $$
が成り立つということである。

各ビットについて

  • SでもTでも立っている
  • Sでのみ立っている
  • SでもTでも立っていない

の3通りの状態がありうるのだから自明ではある。
bitDP回りでよくO(3^N)という数が出てくるのはそのためである。

実際の回し方については
ビットによる部分集合の列挙 - SRM diary(Sigmar) - TopCoder部
の解説がわかりやすい。

意地悪な制約の問題では計算量 O(3^N) では間に合わず、O(N2^N) に下げる工夫が求められたりする。
高速ゼータ変換／高速メビウス変換 - naoya_t@hatenablog
の出番である。