除原理について - kyopro

スナネコです。
競プロ界隈で"除原理"と呼ばれているものについて説明します。
この言葉は厳密な定義があるものではないので、これから説明することは単に「私はこうだと思っている」というお話として聞いてください。

定義

「 $g:=\zeta f$ と $x$ が与えられるので、 $f(x)$ を求めてください」という問題を、
メビウス変換の定義に基づいて $f(x)=\sum_{y\leq x}\mu(x,y)g(y)$ と求めるのが包除原理、
小さい方から順に $f(x)=g(x)-\sum_{y< x}f(y)$ と求めるのが除原理です。
ただし、シグマの中身を定義通りに計算するものだけでなく、和をとる順序を工夫したり状態をまとめたりするものもそれぞれ包除原理、除原理に含めることにします。

例

EDPC Y問題を考えてみます。
(1,1) から (H,W) への経路それぞれに対して、i 番目の壁を通らない、通る、わからないを表す o, x, ? の長さ N の文字列を対応させます。
また、「その文字列になるような経路の個数」をその文字列そのもので表すことにします。
N=3で考えます。求めるものは ooo です。

包除原理は定義通りに書くと ooo=???-(x??+?x?+??x)+(xx?+x?x+?xx)-xxx で、
除原理は ooo=???-oox-oxo-oxx-xoo-xox-xxo-xxx ですね。
このままだとどちらも項の数が $O(2^N)$ になってしまうので計算をまとめる必要があります。
ここでは詳しい説明はしませんが、
包除原理は ooo=(xが偶数個)-(xが奇数個) に
除原理は ooo=???-x??-ox?-oox にまとめるとうまく計算できます。
kiwamachanさんの解説やけんちょんさんの解説は包除原理で、snukeさんの解説やフェネックさんの解説が除原理ですね。読み比べて見てください。

例2

「 $1\leq x,y \leq N$ であって、 $\mathop{gcd}(x,y)=1$ を満たす組 $(x,y)$ の個数 $f(N)$ を求めよ」という問題を考えてみます。
包除原理で考えると、gcdが1の倍数になるケース、2の倍数になるケース、3の倍数になるケース、……を係数の辻褄をあわせながら足し引きすればいいので $\sum_{1\leq d \leq n}\mu(d)\left(\frac{N}{d}\right)^2$ になります。エラトステネスの篩のように計算すれば $O(N\log\log N)$ 、ディリクレ級数の積を考えると $\tilde{O}(N^{2/3})$ で計算できます。
除原理で考えると、全てのケースから、gcdが2になるケース、3になるケース、……を引けばいいので $N^2 - \sum_{2\leq d \leq N}f\left(\left\lfloor\frac{N}{d}\right\rfloor\right)$ になります。これは定義通りにメモ化再帰で計算すると $O(N\log N)$ 、商列挙を組み合わせると $O(N^{3/4})$ 、小さい $x$ での $f(x)$ を別の方法で先に計算しておくことにすれば $\tilde{O}(N^{2/3})$ で計算できます。

計算量

例2で見たとおり、特別な工夫をしない限り除原理の方が包除原理よりも計算量が悪くなることが多いです。
一方で、除原理は排反な事象に分割して計算できればあとは簡単なのに対し、包除原理だと足すのか引くのか何倍するのか係数を考えるところが難しいです。
包除原理がよくわからないと思うときは、いったん除原理で式を立ててゼータ関数(順序集合のなす束の構造)を見極めてからメビウス関数を書き下して包除原理に書き直す、ということもできます。私は包除原理を考えるのは苦手なので、最初は除原理で考えて、計算量が間に合わないときだけ包除原理で考え直すことにしています。

高速メビウス変換

最初の例での ooo=???-x??-ox?-oox という計算方法は、集合に関する高速メビウス変換と同じです。
（もしわからないなら、3次元の立方体の8つの頂点を000,……,111に対応させて、高速ゼータ変換/高速メビウス変換の外側のループを1回進めるごとに、どこの値がどう足し算/引き算されているか図に描いてみてください）
さらに、集合に関する高速メビウス変換は多次元累積和の逆操作でイメージできるものです。（さっきの図は描いてみましたか？）
つまり、多次元累積和の逆変換と高速メビウス変換とこのタイプの除原理はだいたい同じものということになりますね。
約数ゼータ変換/約数メビウス変換も、「素数が2と3しかない世界」を考えてみると、2次元累積和とその逆変換になっていることがわかります。

除原理？

ここまでで説明した私のイメージでは、ABC162E「Sum of gcd of Tuples (Hard)」の公式解説のO(NlogN)解法は除原理だと思うのですが、実際には「約数包除原理」と呼ばれることが多いようです。
"除原理"という言葉を私とは違う意味で使う子もたくさんいるみたいですね。