0.前言
为了照顾基础参差不齐的读者，本文在可能有必要给出证明的地方均给出简要证明。顺便强烈谴责 zythonc 的不证明作风
可能整理得十分杂乱。
1.Euler 变换
1.0.概念
众所周知，一个 EGF 的 $\exp$ 拥有组合意义：把 $n$ 个有标号元素分成若干无标号集合的方案数。
例如，有标号生成森林的 EGF 是有标号生成树 EGF 的 $\exp$，因为生成森林是若干个生成树。
那么元素也无标号呢？我们有 $\prod\limits_i\dfrac{1}{(1-x^{i})^{f_i}}$。
证明：我们枚举集合大小，于是答案为 $\prod\limits_ i\prod\limits_{j={1}}^{f_i}(1+x^{i}+x^{2i}+\dots)$，即得上式。
或者你可以理解为一个无限背包，体积为 $i$ 的有 $f_i$ 种，于是您就可以用它碾掉付公主的背包。
1.1.例题
不过那题还需要一些简易的推导，罗列如下。
$$
\begin{aligned}
&\prod_i\dfrac{1}{(1-x^{i})^{f_i}}\
=&\exp\left(\sum_if_i\ln\dfrac{1}{1-x^{i}}\right)\
=&\exp\left(\sum_if_i\sum_{j}\dfrac{x^{ij}}{j}\right)
\end{aligned}
$$
里面的东西只有 $O(n\log n)$ 项是有效的，可以方便地计算贡献，于是这题就做完了。
2.单位根反演
2.0.概念
式子非常简洁：$[n|k]=\dfrac 1n\sum\limits_ {i=0}^{n-1}\omega_n^{ik}$。
证明：由单位根的性质得当 $[n|k]$ 为假时，RHS 为 $\dfrac 1n\dfrac{1-\omega_n^{nk}}{1-\omega_ n^{k}}=0$；当 $[n|k]$ 为真时，RHS 为 $\dfrac 1n\sum\limits_ {i=0}^{n-1}1=1$，于是定理得证。
它可以用来求形如 $[a\bmod p=b]=[p|a-b]=\dfrac 1p\sum\limits_{i=0}^{p-1}\omega_p^{ia-ib}$ 的式子。
2.1.例题
看一道例题：LOJ #6485。
题目要求 $\sum\limits_ {i=0}^{n}\dbinom nis^{i}a_ i\bmod4$，我们发现它拥有上面提到的同余形式，所以暴力碾式子。
$$
\begin{aligned}
&\sum_ {i=0}^ n\dbinom nis^ i\sum_ {j=0}^ {3a_ i[i\bmod4=j]}\
=&\dfrac14\sum_ {i=0}^ n\dbinom nis^ i\sum_ {j=0}^ 3a_ j\sum_ {k=0}^ 3\omega_ 4^{ik}\omega_ 4^ {-jk}\
=&\dfrac14\sum_ {j=0}^ 3a_ j\sum_ {i=0}^ n\dbinom nis^ i\sum_ {k=0}^ 3\omega_ 4^{ik}\omega_ 4^{-jk}\
=&\dfrac14\sum_ {j=0}^ 3a_ j\sum_ {k=0}^ 3\omega_ 4^{-jk}\sum_ {i=0}^ n\dbinom nis^ i\omega_ 4^ {ik}\
=&\dfrac14\sum_ {j=0}^ 3a_ j\sum_ {k=0}^ 3\omega_ 4^ {-jk}(s\omega_ 4^ k+1)^ n\
\end{aligned}
$$
于是我们求出单位根这题就做完了。
3.二项式反演
3.0.概念
其实这玩意去年就想看……但是懒得学就咕了（
其实就是一个式子：$f(n)=\sum\limits_ {i=0}^ n(-1)^ i\dbinom nig(i)\Leftrightarrow g(n)=\sum\limits_ {i=0}^ n(-1)^ i\dbinom nif(i)$。
可以看出这个式子惊人地对称，证明可以用代数方法，也可以考虑组合意义（即交集的容斥）。
在应用中很少有直接是容斥形式的式子，更常用的是它的推论 $f(n)=\sum\limits_ {i=0}^ n\dbinom nig(i)\Leftrightarrow g(n)=\sum\limits_ {i=0}^ n(-1)^ {n-i}\dbinom nif(i)$ 和 $f(k)=\sum\limits_ {i=k}^ n\dbinom ikg(i)\Leftrightarrow g(k)=\sum\limits_ {i=k}^ n(-1)^ {i-k}\dbinom ikf(i)$。
3.1.例题
放到题目泛刷里了。
4.拉格朗日反演
4.0.概念
首先我们有多项式复合和复合逆的概念：$F(G)=\sum\limits_if_iG(x)^ i$，$F$ 的复合逆 $G$ 满足 $F(G)=G(F)=x$。
首先我们有引理：对于幂级数 $F$ 满足 $[x]F\ne0$，有 $[x^{-1}]F'F^ k=[k=-1]$。
感性理解，$k\ne-1$ 时 LHS 为 $(\dfrac{1}{k+1}F^{k+1})'$，它显然不会有 $x^{-1}$ 这一项，而若 $k=-1$，$[x^{-1}]\dfrac{F'}{F}=[x^ 0]\dfrac{F'}{F/x}$，它显然等于 $1$。
接下来有拉格朗日反演公式：对于幂级数 $F$ 满足 $[x]F\ne0$，设 $G$ 为其复合逆，则 $n[x^ n]F^ k=k[x^{-k}]G^{-n}$。
证明：由于 $G$ 为复合逆，则
$$
\begin{aligned}
F^ k(G)&=x^ k\
\sum_ii([x^ i]F^ k)G^{i-1}G'&=kx^{k-1}\
[x^{-1}]\sum_ii([x^ i]F^ k)G^{i-1-n}G'&=[x^{-1}]kx^{k-1}G^{-n}\
n[x^ n]F^ k&=k[x^{-k}]G^{-n}
\end{aligned}
$$
，证毕。
我们还有一个便于计算的扩展拉格朗日反演，即 $[x^{n}]H(F)=\dfrac1n[x^{n-1}]H'\left(\dfrac x{G}\right)^{n}$（其中 $H$ 为任意幂级数）。证明与朴素拉反类似，请读者自证。
有些情况下朴素拉反不再适用，如 $n=0,k<0$，这时 EI 给出了另类拉格朗日反演：$[x^{n}]F^{k}=[x^{-k-1}]G'G^{-n-1}$。
证明依然与朴素拉反类似，留作习题。另类拉反也有类似扩展拉反的复合形式，即 $[x^{n}]H(F)=[x^{n}]HG'\left(\dfrac xG\right)^{n+1}$。
4.1.例题
试看看！
证明：$\dfrac{1}{\sqrt{1-4x}}\left(\dfrac{1-\sqrt{1-4x}}{2x}\right)^{m}=\sum\limits_n\dbinom{2n+m}{n}x^{n}$（来自[链接登录后可见]）。
由于见到了根号，考虑二叉树方程 $F=x(1+F)^{2}$，它的根为 $F=\dfrac{1-2x+\sqrt{1-4x}}{2x}$，代回上式即得 LHS 为 $\dfrac{(1+F)^{m+1}}{1-F}$。
由另类拉格朗日反演，$[x^{n}]\dfrac{(1+F)^{m+1}}{1-F}=[x^{n}]\dfrac{(1+x)^{m+1}}{1-x}\left(\dfrac{x}{(x+1)^{2}}\right)'(x+1)^{2(n+1)}=[x^{n}] (1+x)^{2n+m}=\dbinom{2n+m}{n}$。
证毕。
还有一道例题放到题目泛刷里了。
5.斯特林反演
5.0.概念
由斯特林数的反转公式有 $f(n)=\sum\limits_ {i=0}^{n}\begin{Bmatrix}n\
i\end{Bmatrix}g(i)=\Leftrightarrow g(n)=\sum\limits_{i=0}^{n}(-1)^{n-i}\begin{bmatrix}n\
i\end{bmatrix}f(i)$。
5.1.例题
暂时没有找到什么很板的题，先咕一会（
