原来的博客太naive了，基本上就是抄课件而且还抄不对
现在学的容斥也没多少，就记一下碰到过的东西。应该没有证明。
子集反演
大概是最显然的反演了？
对以集合为参数的函数 \(f\) 和 \(g\) ，有
\[\large{g(S)=\sum_{T\subseteq S}f(T)\Leftrightarrow f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T)} \]直接奇加偶减就可以理解。
[SHOI2016]黑暗前的幻想乡
直接子集反演，矩阵树定理算就好了。
[ZJOI2016]小星星
通过把正好映射转化成映射子集把状态降维，避免了枚举子集的转移，最后容斥。
二项式反演
经常用来解决要求恰好满足某一条件的问题。
对于函数 \(f\) 和 \(g\) ，有
\[\large{g(n)=\sum_{i=1}^n\binom{n}{i}f(i)\Leftrightarrow f(n)=\sum_{i=1}^n(-1)^{n-i}\binom{n}{i}g(i)} \] \[\large{g(n)=\sum_{i=n}^m\binom{m}{n}f(i)\Leftrightarrow f(n)=\sum_{i=n}^m(-1)^{i-n}\binom{i}{n}g(i)} \]这两种形式本质上是一样的。
为了方便，这两种形式有时被称作至多至少，但两函数之间的关系实际上不能被至多至少与恰好的关系概括。
即它们不是简单前缀和后缀和的关系，而是 \(g\) 钦定一些元素符合条件，其他元素随意。因此系数应加上一个组合数。通过这样的容斥简化计算。
[LJOI2016]成绩比较
二项式反演，每次钦定碾压了多少人，通过容斥得到答案。中间涉及组合计数基础和连续幂次求和。
已经没有什么好害怕的了
排序后钦定有多少组糖果大于药片， \(DP\) 后容斥，同时考虑大于和小于不好 \(DP\) ，只考虑大于的结果，最后统一乘阶乘得到方案数。