题解 快速莫比乌斯/沃尔什变换 (FMT/FWT)

· · 题解

更新了 FWT-xor 地方关于底数选取的讨论。

更好的阅读体验

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。

下面的讲解可能都会带一点集合的味道，但是我不擅长这玩意，有描述不对的地方麻烦指出。

如果我的描述让你感到了疑惑，可以访问 这篇博文 ，也许他的讲解会让你更理解一些。

计算

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 的答案，合并即可。

如图，这个过程可以分成 \log 层来做，箭头就是累加，时间复杂度 \mathcal O(n\log n) 。

考虑反过来的过程，我们就是要通过子集和反推原来的数列，那就把加进来的减回去就好了。

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 的答案。代码类似。

反过来的话是类似的，逐步减去即可。

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。

于是就做完了。

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;
            }
}

感谢阅读。