fwt | qkoqhh - 什么都没有

题目链接

参考链接

http://blog.leanote.com/post/rockdu/TX20

http://vfleaking.blog.uoj.ac/blog/87

http://blog.miskcoo.com/2015/12/inversion-magic-binomial-inversion

前言

之前只学习了 $FWT$ 和 $FMT$ 的模板，对其原理一点都不理解。

有时，一些题目中会涉及到对这些变换的理解和变形，这要求窝必须彻底理解这些变换的原理。

很多博客对这些变换的证明和理解只字不提，经过一番寻找终于找到了一些适合的文章(如上)，经过学习也感受到了这些变换的奇妙之处，这里也来复现他们的证明过程，加深理解。

反演和变换

变换是对数列做一个线性变换，主要形式如下

$g(n)=\sum_ka_{n,k}f(k)$

反演主要满足以下形式

$g(n)=\sum_k a_{n,k}f(k)\leftrightarrow f(n)=\sum_k b_{n,k}g(k)$

由上可见，反演实质上就是一个线性逆变换，那么在做反演和变换时，我们可以将数列看作列向量，即

$G=AF\leftrightarrow F=BG$

定义 $Kronecker’s\,delta$ 函数 $\delta(i,j)=[i=j]$ ，显然

$\delta(i,j)=\sum_k a_{i,k}b_{k,j}$

即

$E=AB$

所以 $Kronecker’s\,delta$ 函数表示成矩阵形式就是单位矩阵

那么，对一个变换，寻求其反演公式，本质就是在求逆矩阵

子集变换和子集反演

子集变换定义如下：

$G(S)=\sum_{T\subset S}F(T)$

为求其反演公式，我们需要找到其逆矩阵，而我们有

$\sum_{T\subset S}(-1)^{|T|}=[|S|=0]$

那么，得到逆变换之后直接开始推导吧

$\begin{aligned} F(S)=&\sum_{R\subset S}[|S|=|R|]F(R) \\=&\sum_{R\subset S}\sum_{T\subset S-R}(-1)^{|T|}F(R) \\=&\sum_{T\subset S}(-1)^{|T|}\sum_{R\subset S-T}F(R) \\=&\sum_{T\subset S}(-1)^{|T|}G(S-T) \\=&\sum_{T\subset S}(-1)^{|S|-|T|}G(T) \end{aligned}$

所以可以得到子集反演公式

$G(S)=\sum_{T\subset S}F(T)\leftrightarrow F(S)=\sum_{T\subset S}(-1)^{|S|-|T|}G(T)$

这个公式也就是我们所熟知的容斥原理

快速莫比乌斯变换(FMT)

快速莫比乌斯变换算是子集变换，他主要解决并集卷积和交集卷积的加速

$c_i=\sum_{j|k=i}a_kb_j\\ c_i=\sum_{j\& k=i}a_kb_j$

先以比较简单的并集为例，我们的目的是使这个式子和 $FFT$ 一样能够经过变换之后直接做乘法，即

$FMT(C)=FMT(A)*FMT(B)$

这个东西其实比较容易构造，事实上

$FMT(A)=\sum_{i\subset S}a_i$

而

$\begin{aligned} FMT(C)=&\sum_{i\subset x}c_i \\=&\sum_{i\subset C}\sum_{j|k=i}a_jb_k \\=&\sum_{j\subset x}a_j\sum_{j\subset x}b_k \\=&FMT(A)*FMT(b) \end{aligned}$