集合幂级数 学习笔记

基本知识

定义

集合幂级数是一种幂级数，简单来说就是在常见的多项式中占位元的指数是一个整数，在集合幂级数中它的指数是一个集合。

基本运算

集合幂级数的加法是平凡的。

集合幂级数的乘法是子集卷积，即对于两个集合幂级数 \(F,G\)，它们乘积的结果为

\[[x^S](F*G)=\sum_{T \subset S} [x^T]F \times[x^{S/T}]G \]

那么这类似于或卷积，但是要求两集合无交。这使得我们直接用 FWT 做或卷积是错的。我们注意到若 \(S\cap T=\emptyset\)，则 \(|S|+|T|=|S\cup T|\)，于是引入额外的占位符 \(y\) 表示 \(|S|\)，那么子集卷积就变成：

\[[x^Sy^{|S|}](F*G)=\sum_{T \subset S}[x^Ty^{|T|}]F\times[x^{S/T}y^{|S/T|}]G \]

从另一个角度看，这其实是把集合和其大小分开了，做乘法时 \(x\) 就正常做或卷积，\(y\) 就正常做和卷积。因为 \(y\) 的指数可以由 \(x\) 求出来，所以下文中通常只讨论 \(x\) 的指数。

函数复合

常见的只有三个：求逆，\(\ln\)，\(\exp\)。

考虑通过上述方法将幂级数的运算变成普通多项式运算，因为多项式方法常数较大，我们一般采用半在线卷积，时间复杂度为 \(O(n^22^n)\)。

以下均假设 \(A(x)\) 是已知，\(B(x)\) 为要求的答案，将 \([x^i]F\) 简记为 \(F_i\)。

求逆

即 \(A(x)B(x)=1\)。

那么对每一位进行分析就是 \(\sum_{i=0}^nA_iB_{n-i}=[n=0]\)。那么容易发现 \(B_0=\dfrac{1}{A_0}，B_i=-\dfrac{1}{A_i}\sum_{j=1}^iA_jB_{i-j}\),。接下来交给半在线卷积。

ln

即 \(B(x)=\ln(A(x))\)，先求导 \(B'(x)=\dfrac{A'(x)}{A(x)}\)，移项得到 \(B'(x)A(x)=A'(x)\)。分析系数：

\[\begin{aligned} \sum_{i=0}^n(i+1)B_{i+1}A_{n-i}&=(n+1)A_{n+1}\\ (n+1)B_{n+1}A_0&=(n+1)A_{n+1}-\sum_{i=0}^{n-1}(i+1)B_{i+1}A_{n-i}\\ B_n&=\dfrac{nA_n-\sum_{i=0}^{n-2}(i+1)B_{i+1}A_{n-i-1}}{nA_0}\\ B_n&=\dfrac{nA_n-\sum_{i=1}^{n-1}iB_{i}A_{n-i}}{nA_0}\\ B_n&=A_n-\dfrac{\sum_{i=1}^{n-1}iB_{i}A_{n-i}}{n}(A_0=1)\\ \end{aligned} \]

exp

即 \(B(x)=e^{A(x)}\)，求导后有 \(B'(x)=B(x)A'(x)\)，分析系数：

\[\begin{aligned} (n+1)B_{n+1}&=\sum_{i=0}^n(n-i+1)B_iA_{n-i+1}\\ nB_n&=\sum_{i=0}^{n-1}(n-i)B_iA_{n-i}\\ nB_n&=\sum_{i=0}^{n-1}iA_iB_{n-i} \end{aligned} \]

复合的组合意义

exp

考虑 \(\exp\) 的展开式：\(\sum_{i} \dfrac{F^i(x)}{i!}\)。

\(F^i(x)\) 表示选取 \(i\) 个无交集合取并，除 \(i!\) 表示不论顺序，那么组合意义就是组合 \(i\) 个无序无交集合，组合表示权值的乘积。

ln

\(\ln\) 是 \(\exp\) 的逆运算，表示将集合拆成若干无序无交集合，且这些集合的组合是当前集合的权值。

半在线技巧

考虑 \(y\) 这个占位元：如果要计算包含 \(y^i\) 的多项式，那么只需要提供 \(y^j(j<i)\) 的多项式。

例题：WC 2018 州区划分

参考资料

集合幂级数在子图计数上的应用 —— Richard_whr