Zeta 变换实例
Zeta 变换的直观解释与典型用法:布尔格 / SOS DP、max 版本、Möbius 反演和一般偏序集。标签 数学 / Zeta 变换 / SOS DP / 布尔格 / 偏序集
本页承接 Zeta 变换 的定义,整理直观解释、布尔格与 SOS DP、max 版本、Möbius 反演和一般偏序集。
标准 Zeta 变换用加法。把加法换成 、、 或其他可合并运算,就得到对应的变体。
直观理解
朴素地看,每次查询主理想都要枚举其中所有元素。Zeta 变换把这批查询一次性预处理成一张表:算完 后,查询任意主理想只需读一个表项。
所有满足 的 组成一个下集,称为 的 主理想。如果查询集合是 个主理想之并,就合并 个表项; 很小时仍然高效。若查询集合不是下集,Zeta 变换本身不够用。
布尔格与 SOS DP
取 为 位掩码按子集关系构成的 布尔格。此时
计算时从 开始,对每一位 ,把所有包含 的 的 加上去掉 后的值。处理完所有位后, 就是所有子集 的和。
这就是 SOS DP,也叫子集 zeta 变换。时间 ,空间 。把加法换成 ,得到子集最大值。
逆变换是 Möbius 变换,竞赛语境里也常笼统地叫 FMT。
最大值版本
把标准 Zeta 变换中的加法换成 ,得到 max-plus Zeta 变换:
它回答的是主理想内的最大值查询。
Möbius 反演
对标准(求和)Zeta 变换,存在 Möbius 反演:
其中 是偏序集的 Möbius 函数。在布尔格上,(当 ),于是反演就是容斥。
需要注意:max-plus 版本一般不可逆,不能直接套 Möbius 反演。求和版和最大值版共享“下集聚合”的结构,但代数性质不同。
一般偏序集
对一般有限偏序集,可以按定义枚举所有 来计算,也可以利用偏序的乘积结构做逐维变换。SOS DP 的高效来自布尔格是 条二元链的乘积;换成其他偏序集时,需要重新分析可分解的结构和合并代价。
常见误解
- 认为 Zeta 变换就是前缀和:前缀和只是全序(链)上的特例。
- 认为所有集合查询都能用 Zeta:它只直接回答下集/主理想查询;任意集合需要额外分解。
- 认为 max 版本也能 Möbius 反演:max-plus 一般不可逆。
- 认为 SOS DP 只能求和:只要运算是可合并的,也可以做 max、min 或其他聚合。