反演

什么是反演

对于已知 \(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\)。

证明：

\[ \begin{aligned} &G_S=\sum_{T\subset S}(-1)^{|T\oplus S|} F_S \\ \Longleftrightarrow& G_S=\sum_{T\subset S}(-1)^{|T\oplus S|} \sum _{R\subset T}F_R \\ \Longleftrightarrow& G_S=\sum_{T\subset S}G_R\sum _{T\subset R,R\subset S}(-1)^{|S\oplus R|} \\ \Longleftrightarrow& G_S=\sum_{T\subset S}G_R\sum _{R\subset (S\oplus T)}(-1)^{|R|} \\ \Longleftrightarrow& \sum _{T\subset S}G_T[S\oplus T=\empty] \end{aligned} \]

成立。

---

莫比乌斯反演

设 \(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)\)。

证明：

\[ \begin{aligned} &G_i=\sum_{j|i}\mu(\frac{i}{j})F(j) \\ \Longleftrightarrow& G_i=\sum_{j|i}\mu(\frac{i}{j})\sum _{k|j}G_k \\ \Longleftrightarrow& G_i=\sum_{j|i}G_j\sum _{k|\frac{i}{j}}\mu(k) \end{aligned} \]

带入上面的 \(\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\)。

证明：

\[ \begin{aligned} &F_i=\sum_i^n (-1)^{i-j} \cdot C(j,i)\cdot G_j \\ \Longleftrightarrow &F_i=\sum_i^n(-1)^{i-j}\cdot C(i,j)\sum_j^nC(j,k)\cdot F_k \\ \Longleftrightarrow& F_i=\sum_0^i F_j\sum_j^iC(i,k)\cdot C(k,j) \cdot (-1)^{i-k} \\ \Longleftrightarrow& \sum_j^iC(i,k)\cdot C(k,j) \cdot (-1)^{i-k}=[i=j] \end{aligned} \]

\(\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]\)