反演
什么是反演
对于已知\(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]\)
待补。。。