子集卷积及其高级运算

## 1.引入 从 [这道题](https://www.luogu.org/problemnew/show/P3781) 和 [这道题](https://www.luogu.org/problemnew/show/P4221) 出来之后，想必大家都对子集变换多多少少有了些许了解。子集运算具体来说是解决以下问题: $$h_S=\sum_{F\oplus G=S} f_F*g_G$$ 其中，$h,f,g$ 为 **集合幂级数** ， $\oplus$ 为某种子集运算。关于集合幂级数的定义详细请参考2015年国家队论文集吕凯风的论文《集合幂级数的性质与应用及其快速算法》 。 对大部分情况可以利用枚举子集做到 $O(3^n)$ 。其中， $n$ 为全集大小。 对于 $\oplus$ 为子集交、并、对称差的问题， [快速沃尔什变换](https://www.luogu.org/problemnew/show/P4717) 能够在 $O(n 2^n)$ 的复杂度内解决。此处并不讨论这些问题。 现在，我们考虑一下变换: $$h_S=\sum_{T\subseteq S} f_T*g_{S\setminus T}$$ 即 $$h_S=\sum_{F\bigcup G=S,F\bigcap G=\emptyset} f_F*g_G$$ 这一变换称为 **子集卷积** 。简单记作 $h=f*g$ 。 对于这个问题，我们可以利用 **集合占位幂级数** 来解决。 ## 2.集合幂级数的简单应用 ### 2.1 集合占位幂级数的定义 设 $\sigma$ 为一个在 $F[[z]]$ (这个是**形式幂级数环**，就是形式幂级数的定义环，你可以直观理解为集合幂级数的每一位由一个常数换成了一个无限位的多项式) 上的集合幂级数。 如果 $\sigma$ 和某个集合幂级数 $f$ 满足: $$\sigma=\sum_{S\in 2^U}f_Sz^{|S|}x^S+\sum_{S\in 2^U} \sum_{k=|S|+1}^\infty \sigma_{S,i}z^ix^S$$ 那么认为 $\sigma$ 是 $f$ 的**集合占位幂级数**。 ### 2.2 用集合占位幂级数解决子集卷积问题 我们考虑先要卷积的集合幂级数转换为集合占位幂级数，然后我们将集合占位幂级数做自己并卷积。我们发现卷积结果的第 $S$ 位的 $z^p$ 系数为子集并为 $S$ ，子集大小之和为 $p$ 的所有集合系数积之和。如果 $|S|=p$ ，那么这两个集合肯定没有交。其余情况都不合法。 因此，我们直接将他们卷积起来，最后取所有 $z^{|S|}x^S$ 项重新组成集合幂级数即可。 由于形式幂级数做乘法时间复杂度为 $O(n^2)$ ，因此这个方法复杂度为 $O(n^2 2^n)$ 。 对形式占位幂级数做子集或卷积可以将每个 $z^p$ 项拆开，分别卷积后再组合起来。 代码: ```cpp inline void mul(int *f,int *g) { static int sigma[1<<MAXN][MAXN],tao[1<<MAXN][MAXN];//定义形式占位幂级数 Rep(i,0,lim) sigma[i][__builtin_popcount(i)]=f[i],//将形式幂级数转化为形式占位幂级数 tao[i][__builtin_popcount(i)]=g[i]; Rep(i,0,n)FMT(sigma,i),FMT(tao,i);//对每个z^i进行莫比乌斯变换 Rep(i,0,n)calc(sigma,tao,i);//将每一项分别卷积 Rep(i,0,n)IFMT(sigma,i);//莫比乌斯反演回来 } ``` ## 3.集合幂级数的高级运用 ### 3.1 乘法逆元 子集卷积是集合幂级数的主要应用。因此，其逆变换有时也会成为求解的目标。具体而言，其逆变换定义为: $$h=f*g\rightarrow f=h/g$$ 由于我们求解子集卷积的时候仅仅是将对应集合占位幂级数对应项的形式幂级数相乘，因此做除法的时候只需要将对应项形式幂级数相除即可。 回想我们在解决形式幂级数的多项式除法的做法。当被除式的常数项不为 $0$ 时，我们选择将被除式求逆元，然后再与除式卷积。那么集合幂级数显然也是可以这样做的。 定义**集合幂级数** $g^{-1}$ 为 $g$ 的乘法逆元，当且仅当 $g*g^{-1}=\epsilon$ 。其中，$*$ 定义为子集卷积， $\epsilon$ 为**集合幂级数乘法单位元**，即 $x^\emptyset$ 。 那么，我们可以将 $g$ 转换为集合占位幂级数，然后对占位幂级数**每一位上的形式幂级数**求逆即可。 由于转换的过程用到了 $O(n)$ 次 $FMT$ ，因此时间复杂度下界为 $O(n^2 2^n)$ 。介于普通 $O(n\log n)$ 多项式求逆算法常数大且局限性大，并且不能够优化复杂度，因此此处可以利用 $O(n^2)$ 的算法递推出逆元。 具体方法很简单。设 $p$ 为要求逆的形式幂级数， $q$ 为其逆元，则有: $$\sum_{i=0}^n q_ip_{n-i}=[n=1]$$ $$q_n=\begin{cases}\frac{1}{p_0}&n=0\\-\frac{1}{p_0}\sum_{i=0}^{n-1}q_ip_{n-i}&,otherwise\end{cases}$$ ### 3.2 Ln和Exp 为了避免 $x^\emptyset $ 项可以无限卷积引起的冲突，以下集合幂级数强制规定 $x^\emptyset=0$ 。 从形式幂级数的 $Exp$ 定义引申可得: $$Exp(F)=\sum_{k=0}^\infty \frac{F^k}{k!}=1+\sum_{k=1}^n \frac{F^k}{k!}$$ 其中，次方操作定义为对自己进行多次子集卷积，即 $F^k=F*F*\cdots*F$ ，共有 $k-1$ 次卷积运算。 由于强制规定 $x^\emptyset$ 项系数为 $0$ ，因此 $Ln(F)$ 其实并没有定义。但是我们可以对 $Ln(F+1)$ 进行定义。 $$Ln(F+1)=\sum_{k=1}^\infty \frac{(-1)^{k+1}}{k}F^k=\sum_{k=1}^n \frac{(-1)^{k+1}}{k}F^k$$ 通过简单计算可以证明这两种运算实际上互为逆运算。 $Ln(F+1)$ 和 $Exp(F) $ 均可以利用集合占位幂级数来进行快速计算，时间复杂度均为 $O(n^2 2^n)$ 。 同样地，为了避免局限性和大常数，求解形式幂级数的 $Ln$ 和 $Exp$ 时最好采用 $O(n^2)$ 递推的形式。 具体的递推方法: #### Ln: 设 $b=Ln(a+1)$ ,则 $$b'=\frac{a'}{a+1}$$ $$b'(a+1)=a'$$ $$b'_k+\sum_{i=0}^{k-1} b_i*'a_{k-i}=a'_k$$ $$(k+1)b_{k+1}+\sum_{i=0}^{k-1} (i+1)b_{i+1}*a_{k-i}=(k+1)a_{k+1}$$ $$b_{k+1}=a_{k+1}-\frac{1}{k+1}\sum_{i=0}^{k-1} (i+1)b_{i+1}*a_{k-i}$$ #### Exp: 设 $b=e^a$ ，则 $$b'=a'b$$ $$b'_k=\sum_{i=0}^k a'_i*b_{k-i}$$ $$(k+1)b_{k+1}=\sum_{i=0}^k (i+1)a_{i+1}*b_{k-i}$$ $$b_{k+1}=\frac{1}{k+1}\sum_{i=0}^k (i+1)a_{i+1}*b_{k-i}$$ 例题可见吕凯风论文集内的例题。 ### 3.3 开根 这个东西和上面的分析是一样的。 同样，算形式幂级数的开根的时候也最好用 $O(n^2)$ 递推。 递推方式: 设 $b=\sqrt a$ ，则 $$b^2=a$$ $$\sum_{i=0}^k b_i* b_{k-i} = a_k$$ $$2b_k * b_0 = a_k - \sum_{i=1}^{k-1} b_i * b_{k-i}$$ $$b_k = \frac{a_k - \sum_{i=1}^{k-1} b_i * b_{k-i}}{2 b_0}$$ 初值为 $b_0 = \sqrt a_0$ ，即二次剩余。 暂时还没找到例题。 ### 3.4 分治卷积 $$f_S=\sum_{T\subsetneq S} f_T*g_{S\setminus T}$$ 或 $$f_S=\sum_{T\subsetneq S,T\not=\emptyset} f_T*f_{S\setminus T}$$ 这样的递推关系都可以用分治卷积解决。 一般来说，形如: $$f_S=a_S+\sum_{T\subsetneq S}b_Tf_T*c_{S\setminus T}g_{S\setminus T}$$ 都可以用分治卷积做到 $O(n^2 2^n)$ 。 具体做法: 转成集合占位幂级数后，依次枚举形式幂级数的次幂，并不断向高位转移。 注意及时清理多余项。 代码可参考[这份](https://www.luogu.org/recordnew/show/7427389)。