二项式反演与容斥

二项式反演容斥原理：|A_1\cup A_2 \cup \cdots \cup A_n| = \sum|A_i| - \sum|A_i\cap A_j| + \cdots + (-1)^n |A_1\cap A_2 \cap \cdots \cap A_n|根据狄摩根律，可以得到\begin{align}|\overline{A_1}\cap \overline{A_2} \cdots \cap \overline{A_n}| =& |\overline{A_1\cup A_2 \cup \cdots \cup A_n}| \\=& |S| - |A_1\cup A_2 \cup \cdots \cup A_n| \\ =& |S| - \sum|A_i| + \sum|A_i\cap A_j| - \cdots - (-1)^n |A_1\cap A_2 \cap \cdots \cap A_n|\end{align}代入补集，可以得到|A_1\cap A_2 \cap \cdots \cap A_n|=|S|-\sum|\overline{A_i}|+\sum|\overline...

Submit