【数论】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$
快速莫比乌斯变换(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; }