包除原理
ある事象の場合の数を直接数えにくい場合に、より小さくてシンプルな数え上げに分割して解く問題分割。部分事象が排反である時は単なる足し算だが、そうでなくても、共通部分が求められるなら包除原理が使える。
$| A \cup B | = |A| + |B| - |A \cap B|$
バイナリ素性の組み合わせで表現するという解釈もできる。
- 000を求めたいが直接求めることが困難である時に、*** - (1** + 1 + *1) + (11 + 1*1 + *11) - (111) を計算する
- 特に1の個数kによって集合のサイズf(k)が決まる場合
- $\sum_k -1^k \binom{n}{k} f(k)$
- https://twitter.com/opt_cp/status/1298569230439157762
- $| \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))に直して包除原理，と考えると簡単
- https://twitter.com/oinori1197/status/1276894798209679360
包除原理 解ける数え上げの範囲を広げよう tsutaj
- https://compro.tsutaj.com//archive/181015_incexc.pdf
- 小さければ全探索
- 対称性によって組み合わせに帰着
- O(2^N)がO(N)になる
- 部分集合それぞれについて包除原理を使うときO(3^N)
- なぜ？ →部分集合の部分集合の数の和
- これは重いI
- 高速メビウス変換はこれをO(N2^N)にできる
関連