AtCoder Beginner Contest 152 F. Tree and Constraints

条件が一つだけの場合を考えてみます。つまりある頂点からある頂点の道の上に黒辺が少なくとも一つある、という条件のもとでの数え上げを考えます。全体から条件を満たさないものを引くことを考えると解けます。

条件が二つある場合を考えます。この場合も同じように考えられます。まず全体から、一つ目の条件を満たさないものを引き、二つ目の条件を満たさないものを引きます。このとき一つ目の条件と二つ目の条件を両方満たさないものを重複して引いてしまったので、一つ目の条件を満たさず二つ目の条件も満たさないものを足せばよいです。

条件が三つ以上も同様ですが、二つ以下の場合に比べると直感的には捉えづらいです。そこで、条件アと条件イを満たすものは「条件イを満たすもの」から「条件アを満たさず条件イを満たすもの」を引いたものである、という基本的な考え方を使って条件を言い換えていきます。このことを使うと「アかつイかつウ」は「イかつウ」引く「アでないかつイかつウ」となります。「イかつウ」は「ウ」引く「イでないかつウ」となります。「イでないかつウ」は「イでない」引く「イでないかつウでない」になります。「ウ」は「全体」引く「ウでない」となります。つまりこれを繰り返すと、最終的に否定命題の連言となります。このことから、一般に条件が連言で表される数え上げは、否定命題の連言の数え上げが解ければよいということになります。否定命題の連言としてありうる二の「命題数」乗の命題がちょうどひとつずつ現れます。その符号は連言で繋がれている命題の数が偶数ならば正号、奇数ならば負号となります。

このようなものの数え方を包除原理と呼びます。天下り的に証明する方法もありますが、ここでは地道に導きました。条件が連言の場合のほかに、選言で表されている場合も似たような方法がとれます。

よってこの問題は、「ある頂点からある頂点の間の辺がすべて白辺である」の形の複数の文の連言を条件とする問題を解けばよいです。これは易しい問題です。

次は、ある頂点間を結ぶ道上の辺の列挙について考えます。深さ優先探索や幅優先探索などのアルゴリズムによって調べることができますが、次のようにもできます。まず適当な頂点を根として根付き木を作ります。このとき各頂点に対して、その頂点の親と、根からの距離、つまり深さを覚えておきます。二頂点の深さを比べて、深い方の頂点を親に持ち上げるということを繰り返します。このようにするとやがて二頂点は合流しますが、この二頂点が辿ってきた道を併せたものがちょうど二頂点を結ぶ道になっています。これをプログラムにすると次のようになります。

int x, y;
while (x != y) {
  if (dep[x] > dep[y]) swap(x, y);
  y = par[y];
}

以上より解くことができました。包除原理は再帰的に書けます。このように書くと自然数の範囲で計算できます。

let g (xs : nat list) : nat = (* xs の否定の連言 *)

let rec f (xs : nat list) (ys : nat list) : nat =
  match xs with
  | [] -> g ys
  | (x :: xs) -> f xs ys - f xs (x :: ys)

包除原理の例

包除原理を使う例としてオイラー関数を取り上げます。$1$ 以上 $n$ 以下の整数のうち $n$ と互いに素な整数の個数はオイラー関数 $\phi(n)$ と呼ばれます。たとえば 120 に対してオイラー関数の値を計算してみます。$120=2 \times 2 \times 2 \times 3 \times 5$ です。つまり「2 で割り切れない」かつ「3 で割り切れない」かつ「5 で割り切れない」ものを数えればよいです。これは連言で表されているので、包除原理より否定命題の連言に言い換えられます。たとえばそれには「2 で割り切れ、かつ 3 で割り切れる」がありますが、これは「6 で割り切れる」と同値なので、$120 / 6 = 20$ 個あります。同様に考えれば答えは

\begin{align}
\phi(120) = 120 - \frac{120}{2} - \frac{120}{3} - \frac{120}{5} + \frac{120}{2 \times 3} + \frac{120}{2 \times 5} + \frac{120}{3 \times 5} - \frac{120}{2 \times 3 \times 5}
\end{align}

です。さらにこの式は簡単にできて

\begin{align}
\phi(120) = 120 \left(1 - \frac{1}{2}\right) \left( 1 - \frac{1}{3}\right) \left( 1 - \frac{1}{5} \right)
\end{align}

になります。余談ですが、$a$ と $b$ が互いに素のとき $\phi(ab)=\phi(a)\phi(b)$ であることを使うと同じように導けます。