快速莫比乌斯变换（FMT）与莫比乌斯反演 例题：树上lcm
快速莫比乌斯变换数学公式
[*]记\(S\)为全集，\(T\)为其子集
\[\begin{align}&zeta变换:F(S)=\sum_{T\subseteq S}f(T)\\ \\&莫比乌斯反演:f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}F(T)\end{align}\]
[*]\(zeta\)变换与\(sosdp\)中的子集求和、超集求和一致，只不过这里的集合范畴不仅限于二进制集合
[*]莫比乌斯反演的作用就在于将超集和或者子集和反演为原来的函数
代码实现（二进制集合）
\(zeta\)变换(子集和)
伪代码：
for 每一位 bit i:
for 每个 mask:
如果 mask 有第 i 位:
F += F代码：
void zeta(vector &f, int n) { for (int i = 0; i < n; i++) { // 枚举每一位 for (int mask = 0; mask < (1
页:
[1]