快速莫比乌斯变换（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\)变换(子集和)

伪代码：

1. for 每一位 bit i:
2.     for 每个 mask:
3.         如果 mask 有第 i 位:
4.             F[mask] += F[mask 去掉第 i 位]

复制代码

代码：
[code]void zeta(vector &f, int n) {    for (int i = 0; i < n; i++) { // 枚举每一位        for (int mask = 0; mask < (1