集合幂级数

定义

是一种占位幂级数。

现在令 \(2^{\mathbf{X}}\)，表示集合 \(\mathbf{X}\) 的所有子集，即 \(\mathbf{X}\) 的幂集。

对于全集 \(\mathbf{U}\)，不妨给其元素标号为 \({0,1,2,3,\cdots,n-1}\)，其中 \(n=\operatorname{Card}(\mathbf{U})\)，即 \(\mathbf{U}\) 的大小。

那么集合幂级数做的事情，就是充当一个函数，在 \(\mathbf{U}\) 的幂集上向数域 \(\mathbf{F}\) 建立映射，也就是 \(2^{\mathbf{U}}\to F\) 的函数。

为了方便表示，然后用 \(f_{\mathbf{U}}=\sum\limits_{\mathbf{S}\subseteq\mathbf{U}}f_{\mathbf{S}}x^{\mathbf{S}}\) 来表示这个函数，下文的 \(\mathbf{S}\) 无特殊说明一概视作 \(\mathbf{U}\) 的子集。

注意此处的 \(x\) 仍然是一个占位符，而且不同于形式幂级数，这个 \(x\) 的数域和值是不太好找。

事实上应该把 \(f_{\mathbf{S}}x^{\mathbf{S}}\) 看作一个整体，表示 \(f_{\mathbf{S}}\) 的取值。

OI 中一般把 \(\mathbf{S}\) 转化为二进制处理，\(\mathbf{S}\to s\) 的转化中，\(s\) 的第 \(k\) 位为一当且仅当 \(\mathbf{S}\) 含有 \(\mathbf{U}\) 中标号为 \(k\) 的元素。

OI 中一般取 \(\mathbf{F}\) 为 \(\mathbb{R}\) 或 \(\mathbb{Z_p}\)，即实数或模 \(p\) 算数，\(p\) 一般是一个大质数。

运算

仿照形式幂级数定义集合幂级数的运算来定义，但要求运算的集合幂级数的全集皆为 \(\mathbf{U}\)。

• 定义加法 \(h=f+g\)：\(h_\mathbf{S}=f_\mathbf{S}+g_\mathbf{S}\)，且显然存在逆元（若 \(\mathbf{F}\) 上存在逆元）。
• 定义卷积 \(h=f*g\)：\(h_\mathbf{S_1}\oplus\mathbf{S_2}=f_\mathbf{S_1}\cdot g_\mathbf{S_2}\)，这就值得琢磨了。

我们肯定希望运算性质尽量好，否则推导时不易变化，所以不妨在此对 \(\oplus\) 和 \(\mathbf{F}\) 域上的 \(\cdot\) 稍加约束。

• 为了使 \(*\) 满足交换律，我们要求 \(\oplus\) 和 \(\cdot\) 满足交换律；
• 为了使 \(*\) 满足结合律，我们要求 \(\oplus\) 和 \(\cdot\) 满足结合律；
• 为了使 \(*\) 满足分配律，我们要求 \(\cdot\) 满足分配律。

同时符合人类直觉的，\(\oplus\) 还需要有单位元，即 \(\varnothing\)，这保证了卷积的单位元是 \(x^\varnothing\)，记作 \(\epsilon\)。

满足上述要求的 \(\cdot\) 及其域 \(\mathbf{F}\) 很多，故不再赘述。

至于 \(\oplus\)，常见的形式有三种，并对应出三种常见的集合幂级数卷积：并卷积、对称差卷积、子集卷积。对应的位运算为：位或、位异或、子集枚举。

快速莫比乌斯变换

即 FMT，或称 SOSDP，也即高维前缀和。

可以做并卷积，原理就是高位前缀和，复杂度 \(\mathcal{O}(n2^n)\)。

容易说明 FMT 是线性变换，故满足 \(\operatorname{FMT}(H)=\operatorname{FMT}(F)\cdot\operatorname{FMT}(G)\)，此处 \(\cdot\) 是对应位置点乘。

快速沃尔什变换

即 FWT，可做并卷积、对称差卷积，原理就是线性代数，复杂度 \(\mathcal{O}(n2^n)\)。

容易说明 FWT 是线性变换，故满足 \(\operatorname{FWT}(H)=\operatorname{FWT}(F)\cdot\operatorname{FWT}(G)\)，此处 \(\cdot\) 是对应位置点乘。

子集卷积

并不存在直接的做法，下面是一个转化的做法。

考虑子集卷积的 \(\mathbf{S_1}\oplus\mathbf{S_2}=\begin{cases}\text{invalid}&(\mathbf{S_1}\cap\mathbf{S_2}\neq\varnothing)\\\mathbf{S_1}\cup\mathbf{S_2}&(\mathbf{S_1}\cap\mathbf{S_2}=\varnothing)\end{cases}\)，可以总结出一个 \(\oplus\) 有效的充要条件：\(\operatorname{Card}(\mathbf{S_1})+\operatorname{Card}(\mathbf{S_2})=\operatorname{Card}(\mathbf{S_1}\cup\mathbf{S_2})\)。

于是可以考虑设立 \(F_i\)，其中 \(i\in\left[0,n\right)\)。每个 \(F_i\) 表示的都是一个集合幂级数，其中 \(\operatorname{Card}(\mathbf{S})=i\) 的位置在这个幂级数中有值，值是对应的 \(f_\mathbf{S}\)。

同理设立 \(G_i\)，然后令 \(H_{i+j}=F_i*G_j\)，其中 \(*\) 是并卷积，于是 \(H_i\) 中 \(\operatorname{Card}(\mathbf{S})=i\) 的位置的值都是真实有效的值，而其余位置实质是 \(\text{invalid}\)。

复杂度是 \(\mathcal{O}(n^22^n)\)。

事实上 \(*\) 也可以是对称差卷积，但是这个玩意儿没并卷积好。

集合占位幂级数

事实上子集卷积处引入了一个新的数学对象：集合占位幂级数。

对于建立在 \(f\) 上的集合占位幂级数 \(F\)，可以描述为：\(F=\sum\limits_{\mathbb{S}\in 2^\mathbf{U}}f_\mathbf{S}z^{\operatorname{Card}(\mathbf{S})}x^\mathbf{S}+\sum_{\mathbf{S}\in 2^\mathbf{U}}\sum\limits_{i=\operatorname{Card}(\mathbf{S})+1}^{+\infty}\sigma_{\mathbf{S},i}z^{i}x^\mathbf{S}\)。

对于 \(f\) 上的集合占位幂级数，满足 \(\forall i>\operatorname{Card}(\mathbf{S}),\sigma_{\mathbf{S},i}=0\)。

一方面，可以将集合占位幂级数近似地当作一个集合幂级数处理，但域 \(\mathbf{F}\) 不是常规数域，而是模 \(x^n\) 意义下的多项式环，容易说明基本是等价的，下文都将采取此思路。

但其实另一方面，也可以将集合占位幂级数近似地当作一个形式幂级数处理，但多项式环将定义在集合幂级数上，同样容易说明基本是等价的，甚至常数会小。

仍然可以根据上述操作建立 \(f\) 的集合占位幂级数 \(F\)，并且可以像形式幂级数一样转化为线性变换后的形式。

Inv & Ln & Exp

接下来无特殊说明皆假定做子集卷积。

现在定义集合幂级数的 Inv & Ln & Exp。

若 \(f*g=\epsilon\)，则记 \(g=f^{-1}\)，即 \(f\) 的逆元。

\(f^{-1}\) 的求解需要用到集合占位幂级数，具体地，将 \(f\) 转为集合占位幂级数 \(F\) 后，根据线性性，可以先做 FMT 变化，然后对变换后每一位求逆，再逆变换求得 \(F^{-1}\)，即可从中提取 \(f^{-1}\)。

注意存在 \(f^{-1}\) 的充要条件是 \(f_\varnothing\neq 0\)。

同理可求 Ln & Exp，故不赘述。

需要指出的是为什么以集合幂级数而非形式幂级数作为外层对象，因为里面的多项式可以暴力做（不是复杂度瓶颈），于是减少了线性变换次数，优化了常数。

Dvt 与 Igt

集合幂级数 \(f\) 的导数可用 \(f_\mathbf{S\setminus\left\{v\right\}}\gets f_\mathbf{S}\) 定义，然而积分却很难说。

所以这一套东西不是完备的。