排容原理 Inclusion Exclusion¶

核心知識點¶

若要找到 \(A\)，找 \(U\) 使 \(A \subseteq U\)，找 \(B = A'\)，最後 \(n(U) - n(B) = n(A)\)。

排容原理，可以把原本難算的東西，拆成兩個或以上易算的集合，再去做排除與融合。

這就和前綴和、差分技巧的思想是一樣的，排容甚至是這兩個技巧的始祖。

通常可以使用文氏圖來輔助思考。

遇到「至少一個」的問題，可以使用 \(n(U) - n(None)\) 來求。

遇到「所有條件都不滿足」的問題，可以使用 \(n(U) - n(\bigcup_{i=1}^{n} A_i)\) 來求。

這類問題可以以差分的想法思考，也就是計算「所有 \(< k\) 的個數」減去「所有 \(\le k\)的個數」。詳細請見差分。

這類問題本質也是排容原理，請見質數因數問題。

TODO

題目	重點
ABC445E Unbalanced ABC Substrings	把出現不同 -> 全部 - 出現相同，用文氏圖炸開排容。

請你扮演這個知識點的老師，按照本文的介紹詮釋這個知識點。若本文知識點有誤，請點出錯誤的地方並予以修正。