1. 容斥原理
1.1 介绍
解决集合内计数问题。
\(S\) 为集合编号集合。
\[\left | \bigcup_{i\in S}A_i \right | =\sum_{T\subseteq S\wedge T\ne \varnothing}^{n}(-1)^{(\left | T \right | -1)}\left | \bigcap_{j\in T}A_j \right | \]
解决集合内计数问题。
\(S\) 为集合编号集合。
\[\left | \bigcup_{i\in S}A_i \right | =\sum_{T\subseteq S\wedge T\ne \varnothing}^{n}(-1)^{(\left | T \right | -1)}\left | \bigcap_{j\in T}A_j \right | \]