NanoApe's Blog

既是咸鱼又是辣鸡

【数论】FMT 和 FWT

NanoApe posted @ 2016年6月30日 16:07 in 蒟蒻不撕烤智熵何来 , 813 阅读

update:16.06.30

 

并卷积

分治乘法

设当前长度为 $2^n$,按第 $n-1$ 位分成两部分(0为左1为右)后计算 $X=(f^L+f^R)*(g^L+g^R)$ 和 $Y=f^R*g^R$,左边等于 $X-Y$,右边等于 $Y$

快速莫比乌斯变换(FMT)

$$F_S=\sum_{T \subseteq S} f_T$$

快速构造:$f_{S \cup i}←f_{S \cup i}+f_S$

快速莫比乌斯反演(FMI)

$$f_S=\sum_{T \subseteq S} (-1)^{|S|-|T|}F_T$$

快速构造:$f_{S \cup i}←f_{S \cup i}-f_S$

 

异或卷积

分治乘法

设当前长度为 $2^n$,按第 $n-1$ 位分成两部分(0为左1为右)后计算 $X=(f^L+f^R)*(g^L+g^R)$ 和 $Y=(f^L-f^R)*(g^L-g^R)$,左边等于 $(X+Y)/2$,右边等于 $(X-Y)/2$

快速沃尔什变换(FWT)

$$F_S=\sum_{T} f_T(-1)^{|S \cap T|}$$

快速构造:$f_{S}←f_S+f_{S \cup i},~f_{S \cup i}←f_S-f_{S \cup i}$

逆操作时最后乘上 $\frac{1}{2^n}$

inline void fwt()
{
	for(int i=1,x,y; i<m; i<<=1) 
		rep(o, 0, m-1) if (o&i) 
			x=f[o-i], y=f[o], 
			f[o-i]=x+y, f[o]=x-y;
}

 

子集卷积(待填坑)


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter