反演

已知$f$ 使得 ${\displaystyle a_n=\sum _{i=0}^{\mathrm{\infty }}{f}_{n,i}\cdot b_i}$

求$g$ 满足 ${\displaystyle b_n=\sum _{i=0}^{\mathrm{\infty }}{g}_{n,i}\cdot a_i}$

有不少的 $f_{n,>n}=0$ 所以$\mathrm{\infty }$ 对应的替换成$n$也是同样道理

有不少文章从意义角度, 或者直接给表达式,让你验证正确性来写的, 而我没有智力, 总觉得很怪和难以理解, 这篇主要通过EGF和假设没有预知能力来写

基本理论

对于一个明确反演, $f$实际是给定的常数序列, 看成矩阵乘法有(其中$a,b$ 为列向量)

$a=M_f\cdot b$

则$b=M_f^{-1}\cdot a=M_g\cdot a$

即$M_f\cdot M_g=I$ (单位矩阵)

即${\displaystyle \sum _{k=0}^{\mathrm{\infty }}{M}_{f,i,k}{M}_{g,k,j}=[i=j]}$ 是充要条件

一般题目中 知道$a$与$f$, 需要求$b$时使用

下面一般步骤首先建立分别的EGF, 然后通过正向得到两个EGF的等价关系, 最后转换等价关系推得逆向的递推式

egf(指数形 生成 函数), 构建EGF:

${\displaystyle F(x)=\sum _{i=0}^{\mathrm{\infty }}{a}_i\frac{x^i}{i!}}$

${\displaystyle G(x)=\sum _{i=0}^{\mathrm{\infty }}{b}_i\frac{x^i}{i!}}$

常见反演

前缀和反演(差分)

从前缀和与差分开始 ${\displaystyle a_n=\sum _{i=0}^{n}1\cdot b_i⟺b_n=a_n-a_{n-1}}$

前缀和差分 本身不需要用到反演知识, 但从性质上也属于一种反演, 作为对比和样例很好说明问题

前缀和 ${\displaystyle a_n=\sum _{i=0}^{n}1\cdot b_i}$

差分 ${\displaystyle b_n=a_n-a_{n-1}}$

以大小为$4$为例 wolframalpha

$M_f={\displaystyle \left(\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 0& 0\\ 1& 1& 1& 0\\ 1& 1& 1& 1\end{array}\right),M_g=\left(\begin{array}{cccc}1& 0& 0& 0\\ -1& 1& 0& 0\\ 0& -1& 1& 0\\ 0& 0& -1& 1\end{array}\right),M_f\cdot M_g=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)}$

---

${\displaystyle F(x)=\sum _{i=0}^{\mathrm{\infty }}(\sum _{j=0}^{i}1\cdot b_j)\frac{x^i}{i!}}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}{b}_j\sum _{i=j}^{\mathrm{\infty }}\frac{x^i}{i!}}$

有${\displaystyle \int F(x)dx=\sum _{j=0}^{\mathrm{\infty }}{b}_j\sum _{i=j}^{\mathrm{\infty }}\frac{x^{i+1}}{(i+1)!}=\sum _{j=0}^{\mathrm{\infty }}{b}_j\sum _{i=j+1}^{\mathrm{\infty }}\frac{x^i}{i!}}$

即 $F(x)-(\int F(x)dx)=\sum _{j=0}^{\mathrm{\infty }}{b}_j(\sum _{i=j}^{\mathrm{\infty }}\frac{x^i}{i!}-\sum _{i=j+1}^{\mathrm{\infty }}\frac{x^i}{i!})=\sum _{j=0}^{\mathrm{\infty }}{b}_j\frac{x^j}{j!}=G(x)$

即${\displaystyle \sum _{i=0}^{\mathrm{\infty }}{b}_i\frac{x^i}{i!}=G(x)=F(x)-(\int F(x)dx)=\sum _{i=0}^{\mathrm{\infty }}(a_i-a_{i-1})\frac{x^i}{i!}}$

同样得到了$b_i=a_i-a_{i-1}$

---

二维前缀和

两个维度在运算上其实互不影响, 所以两个维度的逆运算也是互不影响

二项式反演

$a_n=\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})(-1{)}^i{b}_i\iff b_n=\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})(-1{)}^i{a}_i$

正向

${\displaystyle F(x)=\sum _{i=0}^{\mathrm{\infty }}(\sum _{j=0}^i(\genfrac{}{}{0ex}{}{i}{j})(-1{)}^j{b}_j)\frac{x^i}{i!}}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}(-1{)}^j{b}_j\sum _{i=j}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{i}{j})\frac{x^i}{i!}}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}(-1{)}^j\frac{b_j}{j!}{x}^j\sum _{i=j}^{\mathrm{\infty }}\frac{1}{(i-j)!}{x}^{i-j}}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}(-1{)}^j\frac{b_j}{j!}{x}^j\sum _{i=0}^{\mathrm{\infty }}\frac{1}{i!}{x}^i}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}\frac{b_j}{j!}(-x{)}^j\sum _{i=0}^{\mathrm{\infty }}\frac{1}{i!}{x}^i}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}\frac{b_j}{j!}(-x{)}^j{e}^x}$

${\displaystyle =G(-x)e^x}$

反过来

${\displaystyle \sum _{i=0}^{\mathrm{\infty }}{b}_i\frac{x^i}{i!}=G(x)=F(-x)e^{-(-x)}=F(-x)e^x}$

这里依然可以像上面展开, 但是实际上发现 $G$和$F$之间是相同的转化关系 所以对称直接就有了, 不需要再推一次

另一个形式 $a_n=\sum _{i=n}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{i}{n})b_i\iff b_n=\sum _{i=n}^{\mathrm{\infty }}(-1{)}^{i-n}(\genfrac{}{}{0ex}{}{i}{n})a_i$

${\displaystyle F(x)=\sum _{i=0}^{\mathrm{\infty }}(\sum _{j=i}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{j}{i})b_j)\frac{x^i}{i!}}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}j!b_j\sum _{i=0}^j\frac{x^i}{i!(j-i)!i!}}$

并不能搞, 那就先变形一下$a_n^{\prime }=n!a_n,b_n^{\prime }=n!b_n$

即要证 $a_n^{\prime }=\sum _{i=n}^{\mathrm{\infty }}\frac{b_i^{\prime }}{(i-n)!}\iff b_i^{\prime }=\sum _{i=n}^{\mathrm{\infty }}(-1{)}^{i-n}\frac{a_i^{\prime }}{(i-n)!}$

${\displaystyle F(x)=\sum _{i=0}^{\mathrm{\infty }}(\sum _{j=i}^{\mathrm{\infty }}\frac{b_j^{\prime }}{(j-i)!})\frac{x^i}{i!}}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}{b}_j^{\prime }\sum _{i=0}^j\frac{x^i}{(j-i)!i!}}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}\frac{b_j^{\prime }}{j!}\sum _{i=0}^j(\genfrac{}{}{0ex}{}{j}{i})x^i}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}\frac{b_j^{\prime }}{j!}(1+x{)}^j}$

$=G(1+x)$

反过来

${\displaystyle \sum _{i=0}^{\mathrm{\infty }}{b}_i^{\prime }\frac{x^i}{i!}=G(x)=F(x-1)=\sum _{i=0}^{\mathrm{\infty }}{a}_i^{\prime }\frac{(x-1{)}^i}{i!}}$

${\displaystyle =\sum _{i=0}^{\mathrm{\infty }}{a}_i^{\prime }\frac{\sum _{j=0}^i(\genfrac{}{}{0ex}{}{i}{j})x^j(-1{)}^{i-j}}{i!}}$

${\displaystyle =\sum _{i=0}^{\mathrm{\infty }}{a}_i^{\prime }\sum _{j=0}^i\frac{x^j(-1{)}^{i-j}}{(i-j)!j!}}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}\frac{x^j}{j!}\sum _{i=j}^{\mathrm{\infty }}{a}_i^{\prime }\frac{(-1{)}^{i-j}}{(i-j)!}}$ 得证

注意到 $e^{-x}=\sum \frac{(-x{)}^i}{i!}$, 有些时候$a,b$在下标大于某个值$m$时都是$0$, 所以可以翻转$a_i=a_{m-i}$

相当于$a,b$生成函数之间有 $a(x)=y(x)e^{-x}$, 这里还可以快速对序列 $a$ 和 $b$进行转换

Stirling反演

${\displaystyle a_n=\sum _{k=0}^n\left\{\begin{array}{c}n\\ k\end{array}\right\}{b}_k\iff b_n=\sum _{k=0}^n\left[\begin{array}{c}n\\ k\end{array}\right]a_k}$

注: 这里的 第一类stirling数是带符号的, 如果要写成不带符号的则是$[\begin{array}{c}n\\ k\end{array}](-1{)}^{n-k}$

同样的原理 ${\displaystyle \hat{F}(z)=\hat{G}(e^z-1)}$

---

${\displaystyle F(x)=\sum _{i=0}^{\mathrm{\infty }}(\sum _{j=0}^i\{\begin{array}{c}i\\ j\end{array}\}{b}_j)\frac{x^i}{i!}}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}{b}_j\sum _{i=j}^{\mathrm{\infty }}\{\begin{array}{c}i\\ j\end{array}\}\frac{x^i}{i!}}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}{b}_j\frac{(e^x-1{)}^j}{j!}}$

$=G(e^x-1)$

反过来

${\displaystyle \sum _{i=0}^{\mathrm{\infty }}{b}_i\frac{x^i}{i!}=G(x)=F(\ln (x+1))=\sum _{i=0}^{\mathrm{\infty }}{a}_i\frac{(\ln (x+1){)}^i}{i!}}$

${\displaystyle =\sum _{i=0}^{\mathrm{\infty }}{a}_i(\sum _{j=i}^{\mathrm{\infty }}[\begin{array}{c}j\\ i\end{array}]\frac{x^j}{j!})}$

${\displaystyle =\sum _{j=0}^{\mathrm{\infty }}\frac{x^j}{j!}\sum _{i=0}^j{a}_i[\begin{array}{c}j\\ i\end{array}]}$

莫比乌斯反演

${\displaystyle a_n=\sum _{i\mid n}{b}_i\iff b_n=\sum _{i\mid n}\mu (\frac{n}{i})a_i}$

${\displaystyle b_n=\sum _{i\mid n}{b}_i\cdot [i=n]}$

${\displaystyle =\sum _{i\mid n}{b}_{\frac{n}{i}}\cdot [i=1]}$

${\displaystyle =\sum _{i\mid n}{b}_{\frac{n}{i}}\sum _{d\mid i}\mu (d)}$

${\displaystyle =\sum _{d\mid n}\mu (d)\sum _{d\mid i,i\mid n}{b}_{\frac{n}{i}}}$

${\displaystyle =\sum _{d\mid n}\mu (d)\sum _{d\mid \frac{n}{k},k\mid n}{b}_k}$

${\displaystyle =\sum _{j\mid n}\mu (\frac{n}{j})\sum _{\frac{n}{j}\mid \frac{n}{k},k\mid n}{b}_k}$

${\displaystyle =\sum _{j\mid n}\mu (\frac{n}{j})\sum _{k\mid j}{b}_k}$

${\displaystyle =\sum _{j\mid n}\mu (\frac{n}{j})a_j}$

---

莫反一般配合$[n=1]$使用,

因为${\displaystyle \sum _{d\mid n}\mu (d)=\{\begin{array}{ll}1& \text{if }n=1,\\ 0& \text{if }n>1.\end{array}}$

这个根据wikipedia 似乎也可以 生成函数搞, 但实际操作起来还是 直接推导简单

子集反演

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

核心原理就是奇偶正负抵消

类似 莫比乌斯的$[n=1]$ , 这里需要的工具是${\displaystyle [S=\varnothing ]}$

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

$=\sum _{i=0}^{|S|}(\genfrac{}{}{0ex}{}{|S|}{i})(-1{)}^{|S|-i}$

$=(1-1{)}^{|S|}$

${\displaystyle =[S=\varnothing ]}$

---

因此

${\displaystyle f(S)=\sum _{Q\subseteq S}f(Q)[S-Q=\varnothing ]}$

${\displaystyle =\sum _{Q\subseteq S}f(Q)h(S-Q)}$

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

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

${\displaystyle =\sum _{Q\subseteq S}f(Q)\sum _{Q\subseteq R\subseteq S}(-1{)}^{|S-R|}}$

${\displaystyle =\sum _{R\subseteq S}(-1{)}^{|S-R|}\sum _{Q\subseteq R}f(Q)}$

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

Min-Max容斥

${\displaystyle max(S)=\sum _{T\subseteq S}(-1{)}^{|T|-1}min(T)}$, 核心原理就是奇偶正负抵消

对称 ${\displaystyle min(S)=\sum _{T\subseteq S}(-1{)}^{|T|-1}max(T)}$, 相当于所有元素乘上$-1$

在期望中使用

${\displaystyle E(max(S))=E(\sum _{T\subseteq S}(-1{)}^{|T|-1}min(T))=\sum _{T\subseteq S}(-1{)}^{|T|-1}E(min(T))}$

---

设集合内元素从小到大 排序了

${\displaystyle \sum _{T\subseteq S}(-1{)}^{|T|-1}min(T)}$

${\displaystyle =\sum _{T\subseteq S,a_i=min(T)}(-1{)}^{|T|-1}{a}_i}$, 直接指定$T$

${\displaystyle =\sum _{i=1}^n{a}_i\sum _{T\subseteq S,a_i=min(T)}(-1{)}^{|T|-1}}$, 先指定$a_i$ 再指定$T$

${\displaystyle =\sum _{i=1}^n{a}_i\sum _{j=1}^{n-i+1}\sum _{T\subseteq S,a_i=min(T),|T|=j}(-1{)}^{j-1}}$, 先指定$a_i$, 再指定$T$的大小

${\displaystyle =\sum _{i=1}^n{a}_i\sum _{j=1}^{n-i+1}(-1{)}^{j-1}\sum _{T\subseteq S,a_i=min(T),|T|=j}}$

${\displaystyle =\sum _{i=1}^n{a}_i\sum _{j=1}^{n-i+1}(-1{)}^{j-1}(\genfrac{}{}{0ex}{}{n-i}{j-1})}$

${\displaystyle =\sum _{i=1}^n{a}_i\sum _{j=0}^{n-i}(-1{)}^j(\genfrac{}{}{0ex}{}{n-i}{j})}$

${\displaystyle =\sum _{i=1}^n{a}_i(1-1{)}^{n-i}}$

${\displaystyle =a_n}$

${\displaystyle =max(S_n)}$

单位根反演

FFT

NTT

FWT

示例代码

二项式反演

Stirling反演

莫比乌斯反演

子集反演

Min-Max容斥

单位根反演

FFT

NTT

FWT

相关文章

wikipedia 生成函数反演

https://vfleaking.blog.uoj.ac/slide/87

洛谷 炫酷反演魔术

---

abc 272 中使用二项式反演

abc 278 stirling反演

abc 242 min-max容斥

abc 215 子集反演

莫比乌斯反演