集合幂级数与子集卷积入门

FLY_lai · 2025-02-26 11:05:21 · 算法·理论

集合幂级数

在 FMT 和 FWT 里有提到过。

对于一个序列 a_0\sim a_N，定义一个多元多项式 A(x_1\sim x_n)=\sum_{0\le I<2^{n}}a_I\cdot x_1^{i_1}x_2^{i_2}\cdots x_n^{i_n}，其中 i_1\sim i_n 是 I 这个集合的二进制表示。

这个多项式有 2^n 项，每一项的系数就是 a。这个 A 叫做集合幂级数。可以类比序列对应到 OGF 上，集合就会对应集合幂级数。

相较于 FMT 和 FWT 处，我们进一步定义集合幂级数的乘法。这是一个比较有用的概念。

简记集合幂级数为 A(x)=\sum a_Ix^I，给定 A(x)=\sum_{I}a_Ix^I,B(x)=\sum_{J}a_Jx^J，怎么定义 A(x)\cdot B(x)？

关键在于怎么定义单项式的相乘，也就是 x^I\cdot x^J 怎么定义。在普通单项式乘法里，x^I\cdot x^J=x^{I+J}。但是对于集合幂级数，我们有多种定义。

无论对于哪种定义，都满足交换律和结合律。同时，我们发现这三种定义和与、或、异或卷积都有关系。下面我们来看看。

引理：在 x^I\cdot x^J=x^{I\cup J} 时，A(x)\cdot B(x) 所得的系数刚好是 a,b 的或卷积。

证明：

A(x)\cdot B(x)=(\sum_{I}a_Ix^I)\cdot(\sum_{J}b_Jx^J)=\sum_{I,J}a_Ib_Jx^{I\cup J}=\sum_{K}(\sum_{I\cup J=K}a_Ib_J)x^K

同理，把或卷积替换为与卷积、异或卷积，证明都是类似的。

这个引理表明在做集合幂级数乘法时，仍然可以使用卷积快速求得结果。类比多项式乘法用 FFT 快速计算。

子集卷积

假设我们有两个长为 2^n 的序列 a,b，定义其子集卷积 c=a*b，满足：

c_I=\sum_{J\cup K=I,J\cap K=\empty}a_Jb_K

就是或卷积额外要求其交集为空。也就是要求 J,K 是 I 的划分。

这个问题可以 O(n^2\cdot 2^n) 求，而且有两种解法。

法一

来个新定义。

\begin{cases} a^{(t)}_J=a_J\cdot [|J|=t]\\ b^{(t)}_K=b_K\cdot [|K|=t]\\ \end{cases}

这可以理解为一个拆分，把序列按下标的集合大小分为不同类。

观察到 c_I=\sum_{t=0}^{|I|}\sum_{J\cup K=I}a^{(t)}_Jb^{(|I|-t)}_K。因为 J\cup K=I 且 J\cap K=\empty，所以 |J|+|K|=|I|。于是就可以枚举 |J|=t，则有 |K|=|I|-t。

然后怎么求 c？

将 a^{(t)} 与 b^{(t')} 的或卷积记作 c^{(t,t')}。那么 c_I=\sum_{t+t'=|I|}c^{(t,t')}_I。

容易给出一个算法：

预处理 c^{(t,t')}。
枚举 |I|=i。
枚举 (t,t') 满足 t+t'=i。
将 c^{(t,t')} 中大小为 i 的项加入 c_I。

分析一下复杂度。

第一步预处理，O(n^2\cdot n\cdot 2^n)。之后统计答案，

还是太慢了，我们再来一个优化：

定义 c^{(i)}_I=\sum_{t+t'=i}c^{(t,t')}_I。目标转化为求 c_I^{(0\sim n)}。

那 c^{(i)} 怎么求？

\begin{aligned} c^{(i)}&=\sum_{t+t'=i}c^{(t+t')}\\ &=\mathrm{iDMT}(\mathrm{DMT}(\sum_{t+t'=i}c^{(t,t')}))\\ &=\mathrm{iDMT}(\sum_{t+t'=i}\mathrm{DMT}(c^{(t,t')}))\\ &=\mathrm{iDMT}(\sum_{t+t'=i}\mathrm{DMT}(c^{(t,t')}))\\ &=\mathrm{iDMT}(\sum_{t+t'=i}\mathrm{DMT}(a^{(t)})\cdot \mathrm{DMT}(b^{(t')})) \end{aligned}

注：这里的点乘就是向量点乘。

注 2：这里能把 \mathrm{DMT} 拿进括号里，是因为它是线性变换。

先预处理 a^{(x)},b^{(x)} 的 \mathrm{DMT} 序列，是 O(2n\cdot n\cdot 2^n)=O(n^22^n) 的。

然后 (\sum_{t+t'=i}\mathrm{DMT}(a^{(t)})\cdot \mathrm{DMT}(b^{(t')})) 这一部分的点乘是单次 O(2^n)，总共 O(n2^n) 的。

最后对每个 c^{(i)} 各做一次 \mathrm{iDMT}，单次 O(n2^n)，总共 O(n^22^n)。

总复杂度为 O(n^22^n)。

法二

需要用到占位集合幂级数。这个东西也很有用，对集合幂级数的 exp 和 ln 都有用。

下面给出它的定义。

设有一个长度 2^n 的序列 a_I。定义一个占位集合幂级数 A[z](x_1\cdots x_n)=\sum_{I}a_Ix^Iz^{|I|}，普通集合幂级数就是 A[1](x_1\cdots x_n)。注意 z 对应的是数字而不是集合。

占位集合幂级数也可以定义乘法：x^Iz^u\cdot x^Jz^v=x^{I\cup J}z^{u+v}。对与卷积和异或卷积也是类似的。不过这里要用来解决子集卷积就携程或卷积的形式。

我们定义 x^Iz^u 是合法项，当且仅当 |I|=u。容易发现 I,J 不相交 \iff x^Iz^{|I|}\cdot x^Jz^{|J|} 为合法项。

简写 A[z](x_1\cdots x_n) 为 A[z]。

引理：设 c=a*b（子集卷积），a\rightarrow A[z],b\rightarrow B[z],c\rightarrow C[z]。有：A[z]B[z] 保留合法项后恰为 C[z]。

证明比较显然。不合法项在子集卷积中是不会出现的。

保留合法项是很容易的，只要 O(2^n) 遍历每一项判断即可。那么问题变成求 A[z]B[z]。

法 1

令 A^{(i)} 为 a^{(i)} 的集合幂级数。这个 a^{(i)} 就是在法一中按集合大小分组的 a^{(t)}。B^{(i)} 类似定义。

\begin{cases} A[z]=A^{(0)}+A^{(1)}z+\cdots +A^{(n)}z^n\\ B[z]=B^{(0)}+B^{(1)}z+\cdots +B^{(n)}z^n\\ \end{cases}

枚举 i，对于 A[z]\cdot B[z] 的 z^i 项，包含它的项为 \sum_{t+t'=i}A^{(t)}z^t\cdot B^{(t')}z^{t'}=\sum_{t+t'=i}(A^{(t)}B^{(t')})z^i。

而对于 A^{(t)}B^{(t')} 的处理，我们和上面一样进行 \mathrm{iDMT},\mathrm{DMT}，利用 \mathrm{DMT} 的线性变换性质把集合幂级数的相乘转化为向量的点乘，从而优化复杂度。

具体细节略去。这种方法本质和上面是相同的。不过是引入了 z 作为主元。

法 2

此种方法不同，它并非按 z 分类，而是把 z 看作参数。

把 A[z],B[z] 当作普通的集合幂级数，但是每一项的系数不是一个数，而是一个关于 z 的多项式。

具体而言，A[z]=\sum_{I}(a_Iz^{|I|})x^I，B[z]=\sum_{I}(b_Iz^{|I|})x^I。这里 (a_Iz^{|I|}) 和 (b_Iz^{|I|}) 看作系数。

计算 A[z]B[z]=\mathrm{iDMT}(\mathrm{DMT}(A[z])\cdot \mathrm{DMT}(B[z]))，现在的问题是对于系数是多项式的时候 \mathrm{DMT} 是怎么定义的。

其实没有区别，\overline{a}_I=\sum_{J\subseteq I}a_I，不过前缀和变成了多项式的和。子集反演后也是一样。

复杂度呢？

普通数组做 \mathrm{DMT} 是 O(n2^n) 的，但是现在系数是一个长度为 n 的多项式，所以复杂度是 O(n^22^n) 的。

对 A[z],B[z] 各自求 \mathrm{DMT}，复杂度 O(n^22^n)；让两个结果点乘，复杂度 O(2^n)；对点乘的结果再做 \mathrm{iDMT}，复杂度 O(n^22^n)。注意这里 \mathrm{iDMT} 的复杂度也是平方，因为 \mathrm{iDMT} 也要对多项式运算。