名前がかなり難しそうなのと、実際数式がいっぱいでてくるので(これは私が数学が弱いため)、勉強するのを敬遠してたのですが、 ABC187F - Close Group という問題を彩色数を求めることで解くという解法を解説ページに書いてあったため、せっかくだしやってみようということでちょっと勉強しました。
彩色数を求めるときはどうやら独立集合を $k$ 回使って $S$ の部分集合にするものの個数を求めて、これをメビウス変換すると解けるようです。 いろいろとステップがあるので完全には理解できてはいませんが、とりあえず書けるようにはなったと思います。 まあ彩色数の説明はここではしないんですけどね。
自分用のメモでまとめる程度なので、色々間違ってたりするかもしれませんがご了承を。
ある関数 $f$ と $g$ があって集合 $S$ に対してこのように定義します。
$$\displaystyle f(S) = \sum_{T \subseteq S} g(T)$$ $$g(S) = \sum_{T \subseteq S} (-1)^{|S|-|T|} f(T)$$ このときの $f$ をゼータ変換、 $g$ をメビウス変換というようです。
ゼータ変換とは簡単に何かというと、幅 $2$ の $n$ 次元の累積和を求めることなのだと解釈しました。 $S$ という集合があり、これの部分集合のすべての和を求めるということなので、たしかにそうなっていそうです。
メビウス変換は、累積和からもとの値を求めるものというふうに考えていいかも知れません。差分を求めるので他にも使えそうだけど。
ここでメビウス変換の式を見ると包除原理が使われているようです。これは $2$ 次元累積和から値を求めるときを考えてみるとわかりやすいです。 二次元累積和から値を求めるときは、 $sum[i][j] - (sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1])$ とやりますが、 この時、$sum[i-1][j] + sum[i][j-1]$ をやると、$sum[i-1][j-1]$ の部分についてダブっているので、これを解消するために $sum[i-1][j-1]$ を引くわけです。 ということを考えると、思いっきり包除原理が使われています。そのためこれを一般化すると、さっきの $g$ がでてくるわけです。
しかし、式のままだと、すべての集合について求めたい時高速に求まらないので、 それを速くやりたいということになります。そしてこれが $O(2^N N)$ でできるようです。
とりあえず高速ゼータ変換についてですが、これも累積和であることを意識するとかなり理解しやすくなります。 $2$ 次元累積和を求める時、左から右に一気に求めて、そのあと、上から下へ一気に求めるとすべて求まることがわかります。 この形だと特に重複無しで次元ごとに分けて計算ができるのでそのまま $n$ 次元に適用できます。
つまり、各次元について、$S$ をすべて見て、$S$ についてその次元の $idx$ が $1$ である場合(つまり $idx$ が $S$ に含まれている時) $0$ であるものの要素を足し上げるということをします。 このようにすると、重複無しで $n$ 次元の累積和が求まることがわかります。高速メビウス変換は、これと同じ要領でできて、同じように各次元について見て、$S$ についてその次元の idx が $1$ である場合に $0$ であるものを引けばいいです。 高速ゼータ変換も高速メビウス変換も次元についてのループが外側で回るようにします。
けっこうとっかかりづらかったのですが、実際に勉強してみると、そういうことだったのかとなった。 自分は数式が苦手なので、こういうふうに言葉で書いたり感覚的に理解したりできると嬉しいと思う反面、 もっと深く理解したいなと思うと厳密にやるために数学が必要になるよなぁと思っています。
彩色数もそうだけど、ある集合きっちりになるものの値が求まりづらいから、 部分集合も含めていいという条件で解いておいて、それを後でメビウス変換するという流れになるのかな。