【数论】FMT 和 FWT

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

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$

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

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

$$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$

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

NanoApe's Blog