高速メビウス変換について
高速メビウス変換について自分が勉強した内容をまとめておく。証明はいい感じのサイトを参照のこと。
(http://d.hatena.ne.jp/simezi_tan/20130522/1369203086)
集合に関する関数f,gについて次式が成り立つとき、g(S)が計算できているならば、任意のSについてO(n2^n)でf(S)を計算することができる。
例えば、S={1,2,...,n}として、各i∈Sについて集合A_iが与えられているとき、和集合の要素数を計算したいとする。そして、
は任意のSについて計算が出来たとする。
このとき、
に対して、包除原理の式
を用いると、
となる。これの絶対値を取れば和集合の要素数を得られる。
さて、f(S)は次の漸化式を考えるとf(S)=f_n(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)];