反演

---

什么是反演

对于已知$F_i=\sum a_{i,j}\cdot G_j$

反演得到$G_i=\sum b_{i,j} \cdot F_j$

$\text{NTT,FFT,FWT}$的逆卷积都可以认为是一种反演

---

子集反演

即反解高位前缀和

常见我们写成代码是

void FWT(int n,int *a,int f){
    for(int i=1;i<n;i<<=1) 
        for(int j=1;j<n;++j) if(j&i) 
            a[j]+=a[j^i]*f;
}

$F_S=\sum_{T\subset S}G_T$

则$G_S=\sum_{T\subset S}(-1)^{|T\oplus S|} F_S$

证明

$G_S=\sum_{T\subset S}(-1)^{|T\oplus S|} F_S$

$\Leftrightarrow G_S=\sum_{T\subset S}(-1)^{|T\oplus S|} \sum _{R\subset T}F_R$

$\Leftrightarrow G_S=\sum_{T\subset S}G_R\sum _{T\subset R,R\subset S}(-1)^{|S\oplus R|}$

$\Leftrightarrow G_S=\sum_{T\subset S}G_R\sum _{R\subset (S\oplus T)}(-1)^{|R|}$

$\Leftrightarrow \sum _{T\subset S}G_T[S\oplus T=\empty]$

成立

---

莫比乌斯反演

设$n$的质因数分解为$n=\Pi_1^m p_i^{c_i}$

前置知识：莫比乌斯系数

---

$\mu(n)=\left\{ \begin{aligned} 1 && n=1 \\ (-1)^m && c_i=1 \\ 0 && \exists c_i>1\end{aligned} \right.$

性质：$\sum_{i|n}\mu(i)=[n=1]$

证明：

$\because c_i>1\Rightarrow \mu(n)=0$

$\therefore c_i\in \{0,1\}$

$\therefore \sum _{i|n} \mu(i)=\sum_{S\in\{p_i\} }(-1)^{|S|}=[m=0]$

---

若$F_i=\sum _{j|i}G_i$

则$G_i=\sum_{j|i}\mu(\frac{i} {j})F(j)$

证明

$G_i=\sum_{j|i}\mu(\frac{i} {j})F(j)$

$\Leftrightarrow G_i=\sum_{j|i}\mu(\frac{i} {j})\sum _{k|j}G_k$

$\Leftrightarrow G_i=\sum_{j|i}G_j\sum _{k|\frac{i} {j} }\mu(k)$

带入上面的$\mu(n)$性质，这个式子成立

---

$$\$$

二项式反演

前置知识 $\sum_0^nC(n,i)=[n=0]$

$G_i=\sum _{0}^{i}C(i,j)\cdot F_j$

直接容斥这个式子，就能得到

$F_i=G_i-\sum_{j<i}C(i,j)\cdot F_j$

但是容斥过程是$n^2$的，如果$n$较大，用分治$\text{NTT}$实现也是$n\log ^2n$

所以需要二项式反演

反演:$G_i=\sum _{0}^{i}C(i,j)\cdot F_j\Leftrightarrow F_i=\sum_0^i (-1)^{i-j}\cdot C(i,j)\cdot G_j$

有时候看到是$G_i=\sum _{i}^{n}C(j,i)\cdot F_j\Leftrightarrow F_i=\sum_i^n (-1)^{i-j}\cdot C(j,i)\cdot G_j$

证明

$F_i=\sum_i^n (-1)^{i-j} \cdot C(j,i)\cdot G_j$

$\Leftrightarrow F_i=\sum_i^n(-1)^{i-j}\cdot C(i,j)\sum_j^nC(j,k)\cdot F_k$

$\Leftrightarrow F_i=\sum_0^i F_j\sum_j^iC(i,k)\cdot C(k,j) \cdot (-1)^{i-k}$

$\Leftrightarrow \sum_j^iC(i,k)\cdot C(k,j) \cdot (-1)^{i-k}=[i=j]$

$\because C(i,k)\cdot C(k,j)=\frac{i!} {j!(i-k)!(k-j)!}$

$=\frac{i!} {j!(i-j)!}\cdot \frac{(i-j)!} {(i-k)!(k-j)!}=C(i,j)\cdot C(i-j,i-k)$

$\sum_j^iC(i,k)\cdot C(k,j) \cdot (-1)^{i-k}=C(i,j)\sum_0^{i-j}(-1)^kC(i-j,k)=[i=j]C(i,j)=[i=j]$

---

待补。。。