容斥原理:
错排公式 $f_n=\sum_{i=0}^n(-1)^i\frac{n!}{i!}$=(-1)^n+n*f_{n-1}$
二项式反演 $b_k=\sum_{i=0}^{k}C_k^ia_i \ \ <--> \ \ a_k=\sum_{i=0}^k(-1)^{k-i}C_k^ib_i$ $b_k=\sum_{i=k}^{n}C_i^ka_i \ \ <--> \ \ a_k=\sum_{i=k}^n(-1)^{i-k}C_i^kb_i$
$*$$n \leq 1e9$ 个咸鱼,$m \leq 15$ 个操作, 每次把某个数倍数的咸鱼翻身, 问最后另一面朝上的有多少题解
$*$bzoj4671
$-->\sum_{i=1}^nC_n^i(S_n^i)coef_i$, 暴力求系数
广义容斥原理 m 个元素 n 个性质,$A_k$-- 满足 $k$ 性质的集合,$P_k$-- 满足 $k$ 个性质的元素的元次,$P_k=\sum_{I\in C_n^k}|\bigcap _{i\in I}A_i|$,$Q_k$ 恰好 $k$ 个性质的元素的个数,$Q_k=\sum_{I \in C_n^k}|(\bigcap_{i \in I}A_i) \bigcap (\bigcap_{j \in \bar{I}}\bar{A_j}|$, 有 $Q_k=\sum_{k \leq i \leq n}(-1)^{i-k}C_i^kP_k$
- $*$bzoj3622
- $*$bzoj4559
来源: http://www.bubuko.com/infodetail-2541146.html