包除原理
ある事象の場合の数を直接数えにくい場合に、より小さくてシンプルな数え上げに分割して解く問題分割。部分事象が排反である時は単なる足し算だが、そうでなくても、共通部分が求められるなら包除原理が使える。 $ | A \cup B | = |A| + |B| - |A \cap B|
https://gyazo.com/afe3d4832a4c5543a2d318ddc95e32d7
000を求めたいが直接求めることが困難である時に、*** - (1** + *1* + **1) + (11* + 1*1 + *11) - (111) を計算する
特に1の個数kによって集合のサイズf(k)が決まる場合
$ \sum_k -1^k \binom{n}{k} f(k)
$ | \bigcap_{i \in V}A_i | = \sum_{S \subseteq V} (-1)^{|S|} | \bigcap_{i\in S} A_i^{\mathsf c} |
|A or B| = |A| + |B| - |A and B|と考えるのではなく|¬A and ¬B| = |U| - |A| - |B| + |A and B|と考えると楽 src ABC172E $ | A \cup B | = |A| + |B| - |A \cap B|
$ | A^{\mathsf c} \cap B^{\mathsf c} | = |U| - |A| - |B| + |A \cap B|
事象にちゃんと名前をつけて式変形をする・どの事象が簡単に計算できるかを意識する
今回のN=3とした場合を考える．#()で事象の要素数を表すとする．
Pi = (Ai=Biとなる事象)として，求めたいのは#(¬P1 ∧ ¬P2 ∧ ¬P3)で，簡単に計算できるのは#(P1)とか#(P1 ∧ P2)とか．#(¬P1 ∧ ¬P2)とかは扱いにくいので，ドモルガンで#(¬(P1 ∨ P2 ∨ P3))に直して包除原理，と考えると簡単
小さければ全探索
対称性によって組み合わせに帰着
O(2^N)がO(N)になる
部分集合それぞれについて包除原理を使うときO(3^N)
これは重いI
関連