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

记号

  1. 表示

)表示一个以集合为下标的一一映射(或者说数组)。

集合幂级数

我们定义)的集合幂级数为

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

集合幂级数的基础运算

对于两个上的集合幂级数,他们的加法运算为

也就是对应项系数相加。

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

  1. 交换律:
  2. 结合律:
  3. 单位元:

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

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

集合并

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

为了计算集合并卷积,我们先定义的子集和为

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

时间复杂度

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

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

集合交

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

集合异或

考虑集合异或运算,容易发现这是集合异或卷积。

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

可以发现这是 4 个上的集合幂级数,因此可以得到

那么我们可以计算以及的值,那么两式相加除以 2 得到,相减除以 2 得到。这样我们就把的集合异或卷积分解为两个的集合异或卷积。该算法时间复杂度

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

除法也是可以定义的。

子集卷积

考虑不相交的并。对于集合,如果那么。否则没有定义(严谨地说,若,那么)。为了计算子集卷积,之前的方法是不适用的。我们定义关于集合占位幂级数

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

等价于。因此我们对的集合占位幂级数做集合并卷积得到

那么容易发现

在实现的过程中,我们认为的系数是一个长度的关于的形式幂级数。FMT 可以对应项系数相加,复杂度。然后对应项系数相乘,也就是对应项形式幂级数相乘,时间复杂度。逆变换也是

因此子集卷积的时间复杂度是

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

稍微解释一下形式幂级数求逆的算法。假设我们要对求逆,那么设其逆元为。于是有

因此

递推即可。

集合幂级数的高级运算

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

集合幂级数求导

定义集合幂级数的导数:

因此对于上的集合幂级数有

集合幂级数 exp

形式幂级数的 exp 通常定义在模意义下。而集合运算是在全集的范围内进行的,系数不会收敛。另一方面,子集卷积在每个多项式非空的情况下最多卷次就会收敛,因此我们只考虑的子集卷积的 exp。

定义为

如何计算?对集合占位幂级数两边同时 FMT 得到

是长度为的形式幂级数,因此我们只需要考虑模意义下形式幂级数 exp 即可。

接下来介绍形式幂级数 exp 的算法。首先考虑求导:

,那么考虑的系数,容易得到

这样就可以递推了,时间复杂度

集合幂级数 ln

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

这里是指的项的系数。仍然是使用集合占位幂级数,容易转化为求模意义下。那么我们继续考虑算法。设。那么求导有

,仍然是考虑的系数:

递推即可。

集合幂级数开根

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

分治卷积 1

已知上的集合幂级数,求集合幂级数,其中

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

由于我们只关心的系数,因此可以转化为

那么考虑分治。假设我们求出了的值。那么的贡献是

容易发现这是一个上的集合或卷积,可以计算(也就是令然后对做集合或卷积)。贡献完之后再递归考虑即可。

总时间复杂度

分治卷积 2

考虑递推式

虽然感觉可以直接求通项公式。但还是介绍一下这个方法。我们仍然有的求法。仍然是考虑集合占位多项式。但这次我们先枚举的次数。也就是说。因此我们从小到大枚举,那么这就是集合或卷积的运算。由于对于每个我们会做一次 FMT/IFMT,而我们会做次对应项系数相乘的乘法,因此复杂度仍是

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

参考文献

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

子集卷积及其高级运算