数学笔记
反演和容斥
反演本质
反演形如 \(f(n)=\sum\limits_{i=0}^na_ig(i)\iff g(n)=\sum\limits_{i=0}^nb_if(i)\)。实质是：两个函数（数列）之间的双向（求和）关系。
如果定义一个关系矩阵 \(\mathcal A\)，满足 \(f(n)=\sum\limits_{i=0}^ng(i)\mathcal A_{i,n}\)，考虑其实质是向量 \([f_0,f_1,\dots,f_n]=[g_0,g_1,\dots,g_n]\times\mathcal A\)，即 \(F=G\times\mathcal A\)。此时不难逆向的推出 \(G=F\times\mathcal A^{-1}\)。
于是我们就得到了反演的通项，若 \(A\times B=I\)，则 \(f(n)=\sum\limits_{i=0}^ng(i)A_{i,n}\iff g(n)=\sum\limits_{i=0}^nf(i)B_{i,n}\)。
集合反演
\[f(S)=\sum\limits_{T\subseteq S}g(T)\iff g(S)=\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}f(T)
\]
\[f(S)=\sum\limits_{T\supseteq S}g(T)\iff g(S)=\sum\limits_{T\supseteq S}(-1)^{|T|-|S|}f(T)
\]
二项式反演
\[f(n)=\sum\limits_{i=0}^n\dbinom{n}{i}g(i)\iff g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}f(i)
\]
\[f(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}g(i)\iff g(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}f(i)
\]
莫比乌斯反演
\[f(n)=\sum\limits_{d|n}g(d)\iff g(n)=\sum\limits_{d|n}\mu(d)f(\frac{n}{d})
\]
其中 \(\mu(n)=\begin{cases}0&\exists p\in\mathbb{P},p^2|n\\(-1)^m&otherwise\end{cases}\)，\(m\) 为 \(n\) 的不同质因子数。
Min-Max 容斥
\[\max\limits_kS=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-k}{k-1}\min\limits_kS
\]
\[\min\limits_kS=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-k}{k-1}\max\limits_kS
\]
\[E(\max\limits_kS)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-k}{k-1}E(\min\limits_kS)
\]
\[E(\min\limits_kS)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-k}{k-1}E(\max\limits_kS)
\]