集合幂级数的收敛域如何确定？

本文共计10510个文字，预计阅读时间需要43分钟。

集合层级数相关算法：快速莫比乌斯变换（FMT）、高维前缀和（SOSDP）、快速布尔变换（FWT）、子集卷积（Subset Convolution）+ 更新日志 2022.2.28 + 重构整篇文章。原文见 + 位运算卷积，子集“

集合幂级数相关算法：快速莫比乌斯变换（FMT），高维前缀和（SOSDP），快速沃尔什变换（FWT），子集卷积（Subset Convolution） CHANGE LOG

• 2022.2.28 重构整篇文章。原文章见 位运算卷积，子集卷积与高维前缀和。

NOI 大纲里没有把位运算卷积如 FMT，FWT，子集卷积等知识点单独列出，但高维前缀和（SOSDP）是应用比较广泛的重要算法。

学习上述算法，首先要理解什么是集合幂级数。

1. 集合幂级数 1.1 定义

集合幂级数最初由吕凯风在他的 2015 年集训队论文《集合幂级数的性质与应用及其快速算法》中提出。这个名字听起来非常高级，但实际上不难理解。如果读者能够有一点点形式幂级数的基础知识会更容易理解。

为方便说明，我们引入一些记号：

• 定义 \(2 ^ X\) 表示 \(X\) 的所有幂集，即 \(X\) 的所有子集组成的集合。
• 定义 \(U\) 为全集 \(\{1, 2, \cdots, n\}\)，其中 \(n = |U|\)，即 \(U\) 的大小。用数字来表示元素是因为我们并不关心集合中的元素具体是什么，数字只是一个易于理解的符号。
• 若无特殊说明，\(S\) 均为 \(U\) 的子集。

形式化地，域 \(F\) 上的集合幂级数 \(f\) 是 \(2 ^ U \to F\) 的函数，其中对于每个 \(S \subseteq U\)，函数 \(f\) 均有对应的取值 \(f_S \in F\)。