Zeta 变换实例

Zeta 变换的直观解释与典型用法:布尔格 / SOS DP、max 版本、Möbius 反演和一般偏序集。

标签 数学 / Zeta 变换 / SOS DP / 布尔格 / 偏序集

本页承接 Zeta 变换 的定义,整理直观解释、布尔格与 SOS DP、max 版本、Möbius 反演和一般偏序集。

标准 Zeta 变换用加法。把加法换成 max、min、gcd 或其他可合并运算,就得到对应的变体。

直观理解

朴素地看,每次查询主理想都要枚举其中所有元素。Zeta 变换把这批查询一次性预处理成一张表:算完 𝑍ℎ 后,查询任意主理想只需读一个表项。

所有满足 𝑦≤𝑥 的 𝑦 组成一个下集,称为 𝑥 的 主理想。如果查询集合是 𝑘 个主理想之并,就合并 𝑘 个表项;𝑘 很小时仍然高效。若查询集合不是下集,Zeta 变换本身不够用。

布尔格与 SOS DP

取 𝑃 为 𝐵 位掩码按子集关系构成的 布尔格。此时

𝐹(𝑆)=∑𝑇⊆𝑆𝑓(𝑇)

计算时从 𝐹=𝑓 开始,对每一位 𝑏,把所有包含 𝑏 的 𝑆 的 𝐹(𝑆) 加上去掉 𝑏 后的值。处理完所有位后,𝐹(𝑆) 就是所有子集 𝑇⊆𝑆 的和。

这就是 SOS DP,也叫子集 zeta 变换。时间 𝑂(𝐵2𝐵),空间 𝑂(2𝐵)。把加法换成 max,得到子集最大值。

逆变换是 Möbius 变换,竞赛语境里也常笼统地叫 FMT。

最大值版本

把标准 Zeta 变换中的加法换成 max,得到 max-plus Zeta 变换:

𝑍ℎ(𝑥)=max𝑦≤𝑥ℎ(𝑦)

它回答的是主理想内的最大值查询。

Möbius 反演

对标准(求和)Zeta 变换,存在 Möbius 反演:

𝑓(𝑥)=∑𝑦≤𝑥𝜇(𝑦,𝑥)𝑍𝑓(𝑦)

其中 𝜇 是偏序集的 Möbius 函数。在布尔格上,𝜇(𝑦,𝑥)=(−1)|𝑥|−|𝑦|(当 𝑦⊆𝑥),于是反演就是容斥。

需要注意:max-plus 版本一般不可逆,不能直接套 Möbius 反演。求和版和最大值版共享“下集聚合”的结构,但代数性质不同。

一般偏序集

对一般有限偏序集,可以按定义枚举所有 𝑦≤𝑥 来计算,也可以利用偏序的乘积结构做逐维变换。SOS DP 的高效来自布尔格是 𝐵 条二元链的乘积;换成其他偏序集时,需要重新分析可分解的结构和合并代价。

常见误解

  • 认为 Zeta 变换就是前缀和:前缀和只是全序(链)上的特例。
  • 认为所有集合查询都能用 Zeta:它只直接回答下集/主理想查询;任意集合需要额外分解。
  • 认为 max 版本也能 Möbius 反演:max-plus 一般不可逆。
  • 认为 SOS DP 只能求和:只要运算是可合并的,也可以做 max、min 或其他聚合。
源码位置