容斥原理
考虑一种问题：找出满足 \(n\) 个条件的元素个数。 将每个条件都转化为对应符合该条件的集合 \(A_i\)，问题即转化为求：
\[
|A_1\cup A_2\cup A_3\cdots \cup A_m|
\]
对于这种问题可以用容斥原理解决。 这里给出容斥原理的公式：
\[
\begin{align*}
&|A_1\cup A_2\cup A_3\cdots \cup A_m| \\
=&\sum_{i}{|A_i|} - \sum_{i<j}{|A_i \cap A_j|} + \sum_{i<j<k}{|A_i\cap A_j \cap A_k|} -\\
&\sum_{i<j<k<l}{|A_i \cap A_j \cap A_k \cap A_l|} \cdots&
\end{align*}
\]
即
\[
\begin{align*}
&|A_1\cup A_2\cup A_3\cdots \cup A_m| \\
= &\sum_{S\subseteq\{1,2,\cdots n\}}{(-1)^{Card(S)+1}\bigcap_{i\in S}{A_i}}&
\end{align*}
\]