【数论】FMT 和 FWT
NanoApe
posted @ 2016年6月30日 16:07
in 蒟蒻不撕烤智熵何来
, 4737 阅读
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;
}
子集卷积（待填坑）
NanoApe
ENE>.<~
计数器
157949
分类
搜索
听听看？
最新留言
最新评论
链接
RSS
Sep 19, 2022 12:38:26 AM
Social Study is most important students to all students of AP 10th Class, here we have provided the study material with solved question bank for all government and private school TM, EM, UM and HM students in chapter wise from past years old exams and we have provided the AP 10th Social Model Paper 2023 Pdf suggested by subject experts. AP SSC Social Model Paper All BSEAP 10th class regular and private course students can follow the list of chapters under SSC Social Study to practice study material with previous question bank to get a better score in summative assessment (SA) and formative assessment (FA) SA-1, SA-2, FA-1, FA-2, FA-3, FA-4 along with Assignments exams previously called Unit Test-1, Unit Test-2, Unit Test-3, Unit Test-4 and Three Months.