集合卷积/快速莫比乌斯变换

Author Avatar
Sakits 10月 03, 2018

简介

  用于快速计算集合卷积

集合并卷积

hS=aSbS[ab=S]fagbh_S=\sum_{a\subseteq S}\sum_{b\subseteq S}[a\cup b=S]f_a*g_b

  暴力是O(4n)O(4^n)的。
  计算方法也是把他们各自求点值(莫比乌斯变换),乘起来之后再插值(莫比乌斯反演)回去。
  设 ff 的莫比乌斯变换为 FF,则 FS=xSfxF_S=\sum\limits_{x\subseteq S}f_x
  相反的,FF 的莫比乌斯反演为 ff,根据容斥原理易得 fS=xS(1)SxFxf_S=\sum\limits_{x\subseteq S}(-1)^{|S|-|x|}F_x
  对卷积式两边都做莫比乌斯变换,则有:

HS=aSbS[abS]FaGb=(aSFa)(bSGb)\begin{aligned} H_S&=\sum_{a\subseteq S}\sum_{b\subseteq S}[a\cup b\subseteq S]F_a*G_b\\ &=(\sum_{a\subseteq S}F_a)*(\sum_{b\subseteq S}G_b) \end{aligned}

  那么只要能快速进行莫比乌斯变换/反演就行了。
  暴力的话是O(3n)O(3^n)的,但有更快的做法。
  设 FS(i)=xS[(Sx){1,2,...,i}]fxF_S^{(i)}=\sum\limits_{x\subseteq S}[(S-x)\subseteq \{1,2,...,i\}]f_x

  初始状态FS(0)=fxF_S^{(0)}=f_x
  对于一个不包含{i}\{i\}的集合SS,有FS{i}(i)=FS(i1)+FS{i}(i1)F_{S\cup \{i\}}^{(i)}=F_{S}^{(i-1)}+F_{S\cup \{i\}}^{(i-1)},钦定给前一项塞{i}\{i\},而后一项没有{i}\{i\},所以是对的。
  递推nn次后得到 FS(n)F_S^{(n)} 即为莫比乌斯变换。
  用高维前缀和实现O(n2n)O(n2^n)。每一维地位相同,所以顺序无所谓,第二层循环小的数不会影响到大的数,所以顺序也无所谓,那么莫比乌斯反演直接把系数改成1-1就好了。

inline void FMT(double *f, int o) //o=1为FMT o=-1为IMFT
{
	for(int i=1;i<(1<<n);i<<=1)
	{
		for(int j=0;j<(1<<n);j++)
		if(j&i) f[j]+=f[j^i]*o;
	}
}