高速メビウス変換について

高速メビウス変換について自分が勉強した内容をまとめておく。証明はいい感じのサイトを参照のこと。
(http://d.hatena.ne.jp/simezi_tan/20130522/1369203086)

集合に関する関数f,gについて次式が成り立つとき、g(S)が計算できているならば、任意のSについてO(n2^n)でf(S)を計算することができる。
${ \displaystyle f(S) = \sum_{T \subset S} (-1)^{|S| - |T|} g(T) }$

例えば、S={1,2,...,n}として、各i∈Sについて集合A_iが与えられているとき、和集合の要素数を計算したいとする。そして、
${ \displaystyle g(S) = |\bigcap_{i \subset S} A_i| }$
は任意のSについて計算が出来たとする。
このとき、
${ \displaystyle f(S) = \sum_{T \subset S} (-1)^{|S| - |T|} |\bigcap_{i \subset T} A_i| }$
に対して、包除原理の式
${ \displaystyle |\bigcup_{i \in S} A_i| = \sum_{T \subset S} (-1)^{|T|+1} |\bigcap_{j \in T} A_j| }$
を用いると、
${ \displaystyle f(S) = (-1)^{|S| - 1} |\bigcup_{i \subset S} A_i }$
となる。これの絶対値を取れば和集合の要素数を得られる。

さて、f(S)は次の漸化式を考えるとf(S)=f_n(S)として計算できることが証明できる。
${ \displaystyle f_0(S) = g(S) \\ f_k(S) = f_{k-1}(S) , (k \not\in S) \\ f_k(S) = -f_{k-1}(S-\{k\}) + f_{k-1}(S) , (k \in S) }$

bitDPをすることでこの漸化式はO(n2^n)で計算することができる。

これをそのまま書けば次のようになるはず。

//f[n+1][1<<n]
//f[0][T](=g[T]) は計算済みとする
for(int i=1;i<=n;i++)for(int S=0;S<(1<<n);S++){
    if(S & (1<<i)) f[i][S]=-f[i-1][S^(1<<i)]+f[i-1][S];
    else f[i][S]=f[i-1][S];
}

上のDPでは各iにおいて既に計算したSの値しか参照していないため、一次元配列を使いまわすことができる。

for(int i=0;i<n;i++)for(int S=0;S<(1<<n);S++) if(S & (1<<i)) f[S]-=f[S ^ (1<<i)];