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

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

[c_x=sum_{ioplus j=x}a_ib_j ]

(oplus)(+) 时,这个就是多项式乘法。

FMT/FWT 则是处理 (oplus)( m{or,and,xor}) 时的问题。

快速莫比乌斯变换和莫比乌斯函数/反演并无关系。

FMT 处理 ( m{or/and}) 时的问题,可以看作是集合的 交/并 来看。

FWT 处理 ( m{xor}) 时的问题。但是有时把 FMT 和 FWT 统称为 FWT。

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

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

计算

1.( m or)(并)

[c_x=sum_{i∪j=x}a_ib_j ]

考虑对一个序列 ( ext F) 进行莫比乌斯变换,得到 ( m{FMT(F)}) ,( m F) 序列的第 ( m x) 项记为 ( m{F_x})

如果我们有 ( m{FMT(c)_n=FMT(a)_n*FMT(b)_n}) ,并且可以 ( m{FMT(F)→F}) ,那就可以解决这个问题了。

我们考虑让 ( m{FMT(F)_n=sum_{isubseteq n}F_i})

[egin{aligned} & m{FMT(a)_n*FMT(b)_n}\ & m{=sum_{isubseteq n}a_isum_{jsubseteq n}b_j}\ & m{=sum_{ksubseteq n}sum_{i∪j=k}a_ib_j}\ & m{=FMT(c)_n} end{aligned} ]

交换枚举的那个意义是先枚举 ( m{k=i∪j}),然后再枚举合法的 ( m{i,j}) ,这样和之前的枚举是等价的。

问题就转化为了如何快速变换了,也就是如何快速求子集和。

那我们考虑一种增量构造的方法。

( m{T_n}) 表示 ( m{FMT(F)_n})

新加入第 (i) 个点。

如果不选,那么集合是 不选 (i) 的,答案不会变。

如果选了,那么集合是 选择 (i) 了的, 不选 (i) 时的集合 会成为新的集合的子集,那答案也要对应加上去。

也就是用 选 (i) 的答案加上 不选 (i) 的答案,合并即可。

如图,这个过程可以分成 (log) 层来做,箭头就是累加,时间复杂度 (mathcal O(nlog 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.( m{and})(交)

[c_x=sum_{i∩j=x}a_ib_j ]

( m{or}) 相似地,我们考虑 ( m{FMT(F)_n}=sum_{nsubseteq i}F_i)

[egin{aligned} & m{FMT(a)_n*FMT(b)_n}\ & m{=sum_{nsubseteq i}sum_{nsubseteq j}a_ib_j}\ & m{=sum_{nsubseteq x}sum_{i∩j=x}a_ib_j}\ & m{=FMT(c)_n} end{aligned} ]

最后的改变枚举对象和上面也是类似的,可以不重不漏的枚举到所有的情况,只是换了个形式和 FMT(c) 重合。

也是相似地,我们考虑增量构造的方法求 ( m{sum_{nsubseteq 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.( m{xor})

[c_x=sum_{i xor j=x}a_ib_j ]

这里的 ( m{FWT(F)}) 不太好构造,稍微推导一下这个是怎么来的。

( m{FWT(F)_n=sum_{i=0}^n}g(n,i)F_i) ,这么设的原因是因为 ( m{FWT(F)_n}) 的第 (i) 项的系数肯定只和 (n,i) 线性相关,因为我们没有乘除操作。

然后带入 ( m{FWT(c)_n=FWT(a)_n*FWT(b)_n}) 中。

[egin{aligned} & m{sum_{i=0}^ng(n,i)c_i=sum_{j=0}^ng(n,j)a_jsum_{k=0}^ng(n,k)b_k}\ & m{sum_{i=0}^ng(n,i)sum_{j xor k=i}a_jb_k=sum_{j=0}^ng(n,j)a_jsum_{k=0}^ng(n,k)b_k}\ & m{sum_{j=0}^nsum_{k=0}^ng(n,j xor k)a_jb_k=sum_{j=0}^nsum_{k=0}^ng(n,j)g(n,k)a_jb_k}\ end{aligned} ]

不难发现, ( m{g(n,j xor k)=g(n,j)*g(n,k)}),那接下来要思考的就是啥样的东西会把 ( m{j,k})( m{j xor k}) 联系起来。

虽然确实难想到,但是 ( m{popcount(a)+popcount(b)equiv popcount(a xor b)pmod 2})

所以就有 ( m{g(n,i)=(-1)^{|i∩n|}}) 。这里把 (i,n) 看做集合,实际就是取出了 (i)(n) 是 1 的位数。

那么就可以 ( m{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 进去当底数呢,它不满足 ( m{2^i}= 2^{i mod 2}) ,所以不太行。

综合下来,只有 -1 作为底数,便于计算,也便于进行逆运算。

容易证明 ( m{g(n,i)*g(n,j)=(-1)^{|i∩n|+|j∩n|}=(-1)^{|(i xor j)∩n|}=g(n,i xor j)})

依然仿造 ( m{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 ,就有 ( m{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;
			}
}

感谢阅读。

个人博客地址: www.moyujiang.com 或 moyujiang.top
原文地址:https://www.cnblogs.com/moyujiang/p/14890910.html