8.5 mx 组合专题

· · 算法·理论

容斥原理

设 U 中元素有 n 种不同的属性，而第 i 种属性称为 P_i，拥有属性 P_i 的元素构成集合 S_i，那么

\left | \bigcup _{i=1}^n s_i \right | =\sum_{m=1}^{n} (-1)^{m-1} \sum_{a_i<a_{i+1}}^{} \left | \bigcap _{i=1}^m s_{a_i} \right |

二项式反演

二项式反演的式子具体归纳成两个式子：

f_n=\sum_{i=0}^{n} (-1)^{n-i} C^i_n g_i \Longleftrightarrow g_n=\sum^n_{i=0} C_n^if_i f_k=\sum_{i=k}^{n} (-1)^{i-k} C^i_k g_i \Longleftrightarrow g_n=\sum^n_{i=k} C_k^if_i