集合幂级数学习笔记

在阅读本文之前，如果你对 FMT，FWT，子集卷积等操作不熟悉，可以先阅读集合变换学习笔记。

记号

1. $[n]$表示$\{1,2,\cdots,n\}$。
2. $f_S$（$S\subseteq [n]$）表示一个以集合为下标的一一映射（或者说序列）。

集合幂级数

我们定义$f_S$（$S\subseteq [n]$）的集合幂级数为

$$F(x)=\sum_{S\subseteq [n]}f_Sx^S$$

当然，我们并没有定义$x$的$S$次方的运算。因此你不需要考虑它的具体含义，把$x$当作一个符号即可。

集合幂级数的基础运算

对于两个$[n]$上的集合幂级数$F,G$，他们的加法运算为

$$H(x)=F(x)+G(x)=\sum_{s\subseteq [n]}(f_S+g_S)x^S$$

也就是对应项系数相加。

要定义乘法运算，我们就首先要定义$x$的指数的运算律。我们定义一个集合之间的运算$\otimes$，要求

1. 交换律：$S\otimes T=T\otimes S$。
2. 结合律：$(A\otimes B)\otimes C=A\otimes (B\otimes C)$。
3. 单位元：$A\otimes \varnothing=A$。

那么定义集合幂级数的乘法运算为

$$\begin{aligned} H(x)&=F(x)G(x)\\ &=\left(\sum_{S\subseteq [n]}f_Sx^S\right)\left(\sum_{T\subseteq [n]}g_Tx^T\right)\\ &=\sum_{S\subseteq[n]}\sum_{T\subseteq[n]}(f_Sg_T)x^{S\otimes T} \end{aligned}$$

接下来我们列举一些典型的集合运算的例子。

集合并

考虑集合并$\cup$运算。那么容易发现这是集合并卷积。

为了计算集合并卷积，我们先定义$F(x)=\sum_{S\in[n]}f_Sx^S$的子集和为

$$\check{F}(x)=\sum_{S\subseteq [n]}x^S\sum_{T\subseteq S}f_T$$

子集和可以使用 FMT 或者 FWT 先实现。然后再点值相乘，再做逆变换，即可计算集合并卷积。

时间复杂度$O(n2^n)$。

那么我们定义了乘法，是否可以定义乘法的逆运算——除法？

显然，只要在进行子集和变换后，每一项都有逆元，则除法也是有意义的。

集合交

取补集就是集合并，因此不赘述。

集合异或

考虑集合异或$\oplus$运算，容易发现这是集合异或卷积。

考虑分治多项式乘法。我们把集合分为含$n$和不含$n$的集合。那么可以得到

$$FG =\left(\sum_{S\subseteq[n-1]}f_Sx^S+\sum_{n\in S\subseteq[n]}f_{S}x^{S}\right)\left(\sum_{S\subseteq[n-1]}g_Sx^S+\sum_{n\in S\subseteq[n]}g_{S}x^{S}\right)$$

可以发现这是 4 个$[n-1]$上的集合幂级数，因此可以得到

$$\begin{aligned} FG &=(F_1+x^{ \{n\} }F_2)(G_1+x^{ \{n\} }G_2)\\ &=(F_1G_1+F_2G_2)+x^{\{n\}}(F_1G_2+F_2G_1) \end{aligned}$$

那么我们可以计算$(F_1+F_2)(G_1+G_2)$以及$(F_1-F_2)(G_1-G_2)$的值，那么两式相加除以 2 得到$F_1G_1+F_2G_2$，相减除以 2 得到$F_1G_2+F_2G_1$。这样我们就把$[n]$的集合异或卷积分解为两个$[n-1]$的集合异或卷积。该算法时间复杂度$T(n)=2T(n-1)+O(2^n)=O(n2^n)$。

实现的时候，我们会做 FWT 变换，然后再点值相乘，再逆变换回去。

除法也是可以定义的。

子集卷积

考虑不相交的并。对于集合$S,T$，如果$S\cap T=\varnothing$那么$S\otimes T=S\cup T$。否则没有定义（严谨地说，若$S\cap T\ne \varnothing$，那么$S\otimes T=0$）。为了计算子集卷积，之前的方法是不适用的。我们定义$F(x)$关于$z$的集合占位幂级数$F_z(x)$为

$$F_z(x)=\sum_{S\subseteq[n]}f_Sx^Sz^{|S|}$$

在这里我们仍不考虑$z$的含义，只当它是占位符。

而$[S\cap T=\varnothing][S\cup T=A]$等价于$[|S|+|T|=|A|][S\cup T=A]$。因此我们对$F$和$G$的集合占位幂级数做集合并卷积得到

$$\begin{aligned} F_zG_z&=\left( \sum_{S\subseteq[n]}f_Sx^Sz^{|S|} \right) \left( \sum_{T\subseteq[n]}g_Tx^Tz^{|T|} \right)\\ &=\sum_{S\subseteq[n]}\sum_{T\subseteq[n]}f_Sg_Tx^{S\cup T}z^{|S|+|T|} \end{aligned}$$

那么容易发现$FG=\sum_{S\subseteq[n]} [x^Sz^{|S|}](F_zG_z)$。

在实现的过程中，我们认为$x^S$的系数是一个长度$O(n)$的关于$z$的形式幂级数。FMT 可以对应项系数相加，复杂度$O(n^22^n)$。然后对应项系数相乘，也就是对应项形式幂级数相乘，时间复杂度$O(n^22^n)$。逆变换也是$O(n^22^n)$。

因此子集卷积的时间复杂度是$O(n^22^n)$。

那么子集卷积有除法吗？只要形式幂级数能够求逆即可。形式幂级数能求逆的条件是常数项非 0。因此除法是可以定义的。

稍微解释一下$O(n^2)$形式幂级数求逆的算法。假设我们要对$F(x)=\sum_{i=0}^nf_ix^i$求逆，那么设其逆元为$G(x)$。于是有

$$\forall 0\le j\le n, \sum_{i=0}^jf_ig_{j-i}=[j=0]$$

因此

$$g_j=\begin{cases} 0 & j=0\\ -\frac{1}{f_0}\sum_{i=1}^jf_ig_{j-i} & j>0 \end{cases}$$

递推即可。

集合幂级数的高级运算

接下来我们介绍集合幂级数基于基础运算的高级运算。也基本不会讨论每种集合运算的情况。

集合幂级数求导

定义集合幂级数的导数：

$$cx^S=\sum_{v\in S}cx^{S\setminus\{v\} }$$

因此对于$[n]$上的集合幂级数有

$$F'(x)=\sum_{S\subseteq [n]}x^S\sum_{v\notin S}f_{S\cup\{v\} }$$

集合幂级数 exp

形式幂级数的 exp 通常定义在模$x^n$意义下。而集合运算是在全集的范围内进行的，系数不会收敛。另一方面，子集卷积在每个多项式非空的情况下最多卷$n$次就会收敛，因此我们只考虑$[x^{\varnothing}]F(x)=0$的子集卷积的 exp。

$e^{F(x)}$定义为

$$e^{F(x)}=\sum_{i\ge 0} \frac{F^i(x)}{i!}$$

如何计算$e^{F(x)}$？对集合占位幂级数两边同时 FMT 得到

$$\begin{aligned} \text{FMT}\left(e^{F_z(x)}\right) &=\sum_{i\ge 0}\sum_{S\subseteq[n]}\frac{([x^S]\text{FMT}(F_z))^ix^S}{i!}\\ &=\sum_{S\subseteq[n]}x^S\sum_{i\ge 0}e^{[x^S]\text{FMT}(F_z)} \end{aligned}$$

而$[x^S]\text{FMT}(F_z)$是长度为$O(n)$的形式幂级数，因此我们只需要考虑模$x^{n+1}$意义下形式幂级数 exp 即可。

接下来介绍$O(n^2)$形式幂级数 exp 的算法。首先考虑求导：

$${(e^{A(x)})}'=\frac{\text{d}e^{A(x)}}{\text{d}x}=\frac{\text{d}e^{A(x)}}{\text{d}A(x)}\frac{\text{d}A(x)}{\text{d}}=e^{A(x)}A'(x)$$

设$e^{A(x)}=\sum b_ix^i$，$A(x)=\sum a_ix^i$，那么考虑$x^i$的系数，容易得到

$$b_{i+1}=\frac{1}{i+1}\sum_{j=0}^ib_ja_{i-j+1}(i-j+1)$$

这样就可以递推了，时间复杂度$O(n^2)$。

集合幂级数 ln

同样是子集卷积的 ln，我们定义

$$\ln(1-F(x))=-\sum_{i\ge 1}\frac{F^i(x)}{i}$$

这里$1$是指$x^{\varnothing}$的项的系数。仍然是使用集合占位幂级数，容易转化为求模$x^{n+1}$意义下$\ln ([x^S]\text{FMT}(F_z))$。那么我们继续考虑$O(n^2)$算法。设$[x^S]\text{FMT}(F_z)=1+A(x)$，$A(x)=\sum_{i\ne 0}a_ix^i$。那么求导有

$$\begin{aligned} \ln'(1+A(x))&=\frac{A'(x)}{1+A(x)}\\ \ln'(1+A(x))(1+A(x))&=A'(x) \end{aligned}$$

设$\ln(1+A(x))=\sum b_ix^i$，仍然是考虑$x^i$的系数：

$$b_{i+1}=a_{i+1}-\frac{1}{i+1}\sum_{j=1}^ia_jb_{i-j+1}(i-j+1)$$

递推即可。

集合幂级数开根

可以使用同样的递推方式，不赘述。

分治卷积 1

已知$[n]$上的集合幂级数$G(x)=\sum_{S\subseteq[n]}g_Sx^S$，求集合幂级数$F(x)=\sum_{S\subseteq[n]}f_Sx^S$，其中

$$f_S=\sum_{T\subseteq S}f_Tg_{S\setminus T}$$

这个看着就像一个分治 FFT 的式子，只不过这次的对象换成了集合幂级数。先使用他们的集合占位幂级数表示，得到

$$\begin{aligned} \sum_{S\subseteq[n]}f_Sx^Sz^{|S|} &=\sum_{S\subseteq[n]}x^Sz^{|S|}\sum_{T\subseteq S}f_Tg_{S\setminus T}\\ \sum_{S\cap T=\varnothing} f_{S\cup T}z^{|S\cup T|} &=\sum_{S\cap T=\varnothing}(f_Sx^{S}z^{|S|})(g_{T}x^{T}z^{|T|}) \end{aligned}$$

由于我们只关心$|S|+|T|=|S\cup T|$的系数，因此可以转化为

$$\sum (f_Sx^{S}z^{|S|})(g_{T}x^{T}z^{|T|})=\sum f_{S\cup T}x^{S\cup T}z^{|S| + |T|}$$

那么考虑分治。假设我们求出了$S\subseteq[n-1]$的$f_S$的值。那么$S\subseteq[n-1]$对$\{n\}\subseteq S\subseteq[n]$的贡献是

$$\sum_{S\subseteq[n-1]} (f_Sx^{S}z^{|S|})\sum_{\{n\}\subseteq T\subseteq[n]}(g_{T}x^{T}z^{|T|})=\sum f_{S\cup T}x^{S\cup T}z^{|S| + |T|}$$

容易发现这是一个$[n-1]$上的集合或卷积，可以$O((n-1)2^{n-1})$计算（也就是令$g'_T=g_{T\setminus\{n\} }$然后对$f,g'$做集合或卷积）。贡献完之后再递归考虑$\{n\}\subseteq S\subseteq[n]$的$f_S$即可。

总时间复杂度$T(n)=2T(n-1)+O((n-1)2^{n-1})=O(n^22^n)$。

分治卷积 2

考虑递推式

$$f_S=\sum_{\varnothing \subset T\subseteq S}f_Tf_{S\setminus T}$$

虽然感觉可以直接求通项公式。但还是介绍一下这个方法。我们仍然有$O(n^22^n)$的求法。仍然是考虑集合占位多项式。但这次我们先枚举$z$的次数。也就是说$(f_Sz^{|S|}x^S)(f_Tz^{|T|}x^T)\to f_{S\cup T}z^{|S| + |T|}x^{S\cup T}$。因此我们从小到大枚举$|S|$和$|T|$，那么这就是集合或卷积的运算。由于对于每个$|S|$我们会做一次 FMT/IFMT，而我们会做$O(n^2)$次对应项系数相乘的乘法，因此复杂度仍是$O(n^22^n)$。

这个方法似乎也可以用于求解上一个分治卷积问题。

参考文献

吕凯风，集合幂级数的性质与应用及其快速算法，2015 年信息学奥林匹克中国国家队候选队员论文集

子集卷积及其高级运算