反演主要用于替换组合式求和，重点在于推式子，原理暂略。

二项式反演

形式 $0$：

$$g(n)=\sum _{i=0}^n(-1{)}^i{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}f(i)\iff f(n)=\sum _{i=0}^n(-1{)}^i{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}g(i)$$

形式 $1$：

$$g(n)=\sum _{i=0}^n{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}f(i)\iff f(n)=\sum _{i=0}^n(-1{)}^{n-i}{\displaystyle (\genfrac{}{}{0ex}{}{n}{i})}g(i)$$

形式 $2$：

$$g(n)=\sum _{i=n}^{\infty }{\displaystyle (\genfrac{}{}{0ex}{}{i}{n})}f(i)\iff f(n)=\sum _{i=n}^{\infty }(-1{)}^{i-n}{\displaystyle (\genfrac{}{}{0ex}{}{i}{n})}g(i)$$

欧拉反演

$$n=\sum _{d\mid n}\phi (d)$$

莫比乌斯反演

$$g(n)=\sum _{d\mid n}f(d)\iff f(n)=\sum _{d\mid n}\mu (d)g(\frac{n}{d})$$

特殊地，$\sum _{d\mid n}\mu (d)=[n=1]$

更特殊地，$\sum _{d\mid gcd(i,j)}\mu (d)=[gcd(i,j)=1]$

子集反演

$$g(S)=\sum _{T\subseteq S}f(T)$$

可得反演式：

$$f(S)=\sum _{T\subseteq S}(-1{)}^{|S|-|T|}g(T)$$

以及：

$$f(T)=\sum _{T\subseteq S}(-1{)}^{|S|-|T|}g(S)$$

单位根反演

$${\displaystyle \frac{1}{m}}\sum _{i=0}^{m-1}({\omega }_m{)}^{i\times d}=[m\mid d]$$

扩展到 $dmodm=k$ 的情况：

$${\displaystyle \frac{1}{m}}\sum _{i=0}^{m-1}{\omega }_m^{i\times (d-k)}=[dmodm=k]$$

把这个形式放到多项式上：对于多项式：$f(x)=\sum _{i=0}^n{a}_i{x}^i$，求其所有下标同余 $m$ 的系数之和。

$$\begin{gathered} \sum _{i=0}^n{a}_i[imodm=k]=\sum _{i=0}^n{a}_i{\displaystyle \frac{1}{m}}\sum _{j=0}^{m-1}{\omega }_m^{j\times (i-k)} \\ ={\displaystyle \frac{1}{m}}\sum _{i=0}^{m-1}{\omega }_m^{-ik}\sum _{j=0}^n{a}_j({\omega }_m^i{)}^j={\displaystyle \frac{1}{m}}\sum _{i=0}^{m-1}{\omega }_m^{-ik}f({\omega }_m^i) \end{gathered}$$

时间复杂度：$O(mT(n))$，其中 $T(n)$ 表示多项式单点求值的时间复杂度。

斯特林反演

$$f(n)=\sum _{i=0}^n\left\{\begin{array}{c}n\\ i\end{array}\right\}g(i)\iff g(n)=\sum _{i=0}^n(-1{)}^{n-i}\left[\begin{array}{c}n\\ i\end{array}\right]f(i)$$