题解 快速莫比乌斯/沃尔什变换 (FMT/FWT)
摸鱼酱
2021-03-25 20:48:51
更新了 FWT-xor 地方关于底数选取的讨论。
[更好的阅读体验](https://www.moyujiang.com/964.html)
$$
c_x=\sum_{i\oplus j=x}a_ib_j
$$
当 $\oplus$ 为 $+$ 时,这个就是多项式乘法。
FMT/FWT 则是处理 $\oplus$ 为 $\rm{or,and,xor}$ 时的问题。
快速莫比乌斯变换和莫比乌斯函数/反演并无关系。
FMT 处理 $\rm{or/and}$ 时的问题,可以看作是集合的 交/并 来看。
FWT 处理 $\rm{xor}$ 时的问题。但是有时把 FMT 和 FWT 统称为 FWT。
下面的讲解可能都会带一点集合的味道,但是我不擅长这玩意,有描述不对的地方麻烦指出。
如果我的描述让你感到了疑惑,可以访问 [这篇博文](http://blog.leanote.com/post/rockdu/TX200) ,也许他的讲解会让你更理解一些。
计算
### 1.$\rm or$(并)
$$
c_x=\sum_{i∪j=x}a_ib_j
$$
考虑对一个序列 $\text F$ 进行莫比乌斯变换,得到 $\rm{FMT(F)}$ ,$\rm F$ 序列的第 $\rm x$ 项记为 $\rm{F_x}$。
如果我们有 $\rm{FMT(c)_n=FMT(a)_n*FMT(b)_n}$ ,并且可以 $\rm{FMT(F)→F}$ ,那就可以解决这个问题了。
我们考虑让 $\rm{FMT(F)_n=\sum_{i\subseteq n}F_i}$。
$$
\begin{aligned}
&\rm{FMT(a)_n*FMT(b)_n}\\
&\rm{=\sum_{i\subseteq n}a_i\sum_{j\subseteq n}b_j}\\
&\rm{=\sum_{k\subseteq n}\sum_{i∪j=k}a_ib_j}\\
&\rm{=FMT(c)_n}
\end{aligned}
$$
交换枚举的那个意义是先枚举 $\rm{k=i∪j}$,然后再枚举合法的 $\rm{i,j}$ ,这样和之前的枚举是等价的。
问题就转化为了如何快速变换了,也就是如何快速求子集和。
那我们考虑一种增量构造的方法。
令 $\rm{T_n}$ 表示 $\rm{FMT(F)_n}$ 。
新加入第 $i$ 个点。
如果不选,那么集合是 不选 $i$ 的,答案不会变。
如果选了,那么集合是 选择 $i$ 了的, 不选 $i$ 时的集合 会成为新的集合的子集,那答案也要对应加上去。
也就是用 选 $i$ 的答案加上 不选 $i$ 的答案,合并即可。
![](https://cdn.jsdelivr.net/gh/moyujiang/piccdn@0deea81e54dbcda77de29942de118c634dfc4639/2021/03/25/134266399e1bf062675ea6453f20bb96.png)
如图,这个过程可以分成 $\log$ 层来做,箭头就是累加,时间复杂度 $\mathcal O(n\log n)$ 。
考虑反过来的过程,我们就是要通过子集和反推原来的数列,那就把加进来的减回去就好了。
```cpp
void FMT_or(int *f,int n,int op){//op=1 FMT op=-1 IFMT
for(int i=1;i<n;i<<=1)
for(int o=i<<1,j=0;j<n;j+=o)
for(int k=0;k<i;k++)
(f[i+j+k]+=f[j+k]*op+p)%=p;
}
```
----------
### 2.$\rm{and}$(交)
$$
c_x=\sum_{i∩j=x}a_ib_j
$$
和 $\rm{or}$ 相似地,我们考虑 $\rm{FMT(F)_n}=\sum_{n\subseteq i}F_i$。
$$
\begin{aligned}
&\rm{FMT(a)_n*FMT(b)_n}\\
&\rm{=\sum_{n\subseteq i}\sum_{n\subseteq j}a_ib_j}\\
&\rm{=\sum_{n\subseteq x}\sum_{i∩j=x}a_ib_j}\\
&\rm{=FMT(c)_n}
\end{aligned}
$$
最后的改变枚举对象和上面也是类似的,可以不重不漏的枚举到所有的情况,只是换了个形式和 FMT(c) 重合。
也是相似地,我们考虑增量构造的方法求 $\rm{\sum_{n\subseteq i}F_i}$。
新加入一个元素 $i$ 。
如果 选 $i$ ,对应的集合和答案都不会变。
如果 不选 $i$ ,集合在 $i$ 这一位就对应 0 ,也就是缩小了,会成为 选 $i$ 对应集合的子集。
由于求和方式的不同,和上面相反,这里需要的是用 不选 $i$ 的答案加上 选 $i$ 的答案。代码类似。
反过来的话是类似的,逐步减去即可。
```cpp
void FMT_and(int *f,int n,int op){//op=1 FMT op=-1 IFMT
for(int i=1;i<n;i<<=1)
for(int o=i<<1,j=0;j<n;j+=o)
for(int k=0;k<i;k++)
(f[j+k]+=f[i+j+k]*op+p)%=p;
}
```
--------------
### 3.$\rm{xor}$
$$
c_x=\sum_{i\ xor\ j=x}a_ib_j
$$
这里的 $\rm{FWT(F)}$ 不太好构造,稍微推导一下这个是怎么来的。
设 $\rm{FWT(F)_n=\sum_{i=0}^n}g(n,i)F_i$ ,这么设的原因是因为 $\rm{FWT(F)_n}$ 的第 $i$ 项的系数肯定只和 $n,i$ 线性相关,因为我们没有乘除操作。
然后带入 $\rm{FWT(c)_n=FWT(a)_n*FWT(b)_n}$ 中。
$$
\begin{aligned}
&\rm{\sum_{i=0}^ng(n,i)c_i=\sum_{j=0}^ng(n,j)a_j\sum_{k=0}^ng(n,k)b_k}\\
&\rm{\sum_{i=0}^ng(n,i)\sum_{j\ xor\ k=i}a_jb_k=\sum_{j=0}^ng(n,j)a_j\sum_{k=0}^ng(n,k)b_k}\\
&\rm{\sum_{j=0}^n\sum_{k=0}^ng(n,j\ xor \ k)a_jb_k=\sum_{j=0}^n\sum_{k=0}^ng(n,j)g(n,k)a_jb_k}\\
\end{aligned}
$$
不难发现, $\rm{g(n,j\ xor\ k)=g(n,j)*g(n,k)}$,那接下来要思考的就是啥样的东西会把 $\rm{j,k}$ 和 $\rm{j\ xor\ k}$ 联系起来。
虽然确实难想到,但是 $\rm{popcount(a)+popcount(b)\equiv popcount(a\ xor\ b)\pmod 2}$ 。
所以就有 $\rm{g(n,i)=(-1)^{|i∩n|}}$ 。这里把 $i,n$ 看做集合,实际就是取出了 $i$ 中 $n$ 是 1 的位数。
那么就可以 $\rm{FWT(F)_x=\sum_{i=0}^n(-1)^{|i∩x|}F_i}$。
按道理,这里的 -1 是可以换成任意数的,但是稍微把 0,1 这种数带进去就知道有问题。问题出在哪呢?
我们定义 g 的时候就说了,它和 n,i 线性相关,但是当底数是 0,1 的时候,它似乎和 n,i 不太相关。0 只有它的 0 次幂可以定义为 1,但计算起来就会出问题。1 的任何整数次幂都是 1,所以完全和指数没有关系。
那如果放 2 进去当底数呢,它不满足 $\rm{2^i}= 2^{i\ mod\ 2}$ ,所以不太行。
综合下来,只有 -1 作为底数,便于计算,也便于进行逆运算。
容易证明 $\rm{g(n,i)*g(n,j)=(-1)^{|i∩n|+|j∩n|}=(-1)^{|(i\ xor\ j)∩n|}=g(n,i\ xor\ j)}$ 。
依然仿造 $\rm{FMT}$ 考虑增量构造方法。
新加入一位 $i$ ,分选或者不选考虑。
选。和选的集合取并,大小不变。和不选的集合取并,大小 -1 。
不选。和选的集合取并,大小不变。和不选的集合取并,大小也不变。
所以 $i$ 这一位如果 选 ,那会累加到原来的 选 上,累减到原来的 不选 上。
如果 不选,那会累加到原来的选和不选上。
也就是 `int x=f[j+k],y=f[i+j+k];f[i+j+k]=x-y,f[j+k]=x+y `,就有 $\rm{FFT}$ 那种感觉了。
逆变换的话是反过来,移一下项,`f[i+j+k]=(x-y)/2,f[j+k]=(x+y)/2`。
于是就做完了。
```cpp
void FWT_xor(int *f,int n,int op){//op=1 FWT op=-1 IFWT
for(int i=1;i<n;i<<=1)
for(int o=i<<1,j=0;j<n;j+=o)
for(int k=0;k<i;k++){
int x=f[j+k],y=f[i+j+k];
f[j+k]=(x+y)%p,f[i+j+k]=(x-y+p)%p;
if(op==-1)(f[j+k]*=inv2)%=p,(f[i+j+k]*=inv2)%=p;
}
}
```
--------
感谢阅读。