推荐学习博客
反演，就是讲一个函数乘一个矩阵变为另一个函数，逆反演就是乘逆矩阵。
二项式反演
\(F(n)=\sum\limits_{i=0}^{n} \binom{n}{i} G(i)\) \(<---->\) \(G(n)=\sum\limits_{i=0}^{n}(-1)^{n-i}\binom{n}{i}F(i)\)
考虑生成函数的证明。
\[F[n]=\sum\limits_{i=0}^{n}\binom{n}{i}G[i]\\
\frac{F[n]}{n!}=\sum\limits_{i=0}^{n}\frac{1}{(n-i)!}\frac{G[i]}{i!}
\]
因为 \(e^x=\sum\limits_{i=0}\frac{x^i}{i!}\)
\[G\times e^x = F \to G = F\times e^{-x}
\]
于是
\[\frac{G[n]}{n!}=\sum\limits_{i=0}^{n}\frac{(-1)^{n-i}}{(n-i)!}\frac{F[i]}{i!}\\
G[n]=\sum\limits_{i=0}^{n}(-1)^{n-i}\binom{n}{i}F[i]
\]
Min-Max 反演
\[Max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}Min(T)
\]
相反也同样成立，可以用容斥证明。
在期望下也同样成立！
拓展minmax容斥：
不证了。
\[Kthmax(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}Min(T)
\]
未完待续...