集合幂级数&FMT 学习笔记

1. 定义

设全集 $U=\{1,2,3,\dots,n\}$ 和环 $R$（例如全体整数和加法、乘法构成的整数环）。在 $U$ 和 $R$ 上定义集合幂级数 $F$ 为从 $S\subseteq U$ 到 $R$ 的映射，即一个大小为 $2^n$ 的数组，$F_i$ 为 $i$ 对应的集合 $S$（用二进制表示每个元素是否存在）映射到的 $R$ 中的元素。

定义集合幂级数间的运算：

• 加法：$(F+G)_S=F_S+G_S$；
• 并乘法：$(F*G)_S=\sum\limits_{X,Y\subseteq U,X\cup Y =S}F_XG_Y$；
• 乘法（无交并乘法）：$(F\times G)_S=\sum\limits_{X\subseteq S} F_XG_{S-X}$

2. 高维前缀和（FMT）

定义集合幂级数的高维前缀和（FMT）：

$\text{FMT}(F)_S=\sum\limits_{T\subseteq S} F_T$

显然可以在 $O(n2^n)$ 的复杂度内求出，而其逆变换 $\text{IFMT}$ 也可以在 $O(n2^n)$ 的复杂度内完成。

考虑其性质：

• $\text{FMT}(F+G)_S=\sum\limits_{T\subseteq S}F_T+G_T=\text{FMT}(F)+\text{FMT}(G)$；
• $\text{FMT}(F*G)_S=\sum\limits_{T\subseteq S}\sum\limits_{X,Y\subseteq U,X\cup Y = T} F_XG_Y=\sum\limits_{X,Y\subseteq U,X\cup Y\subseteq S} F_XG_Y=\text{FMT}(F)_S\times \text{FMT}(G)_S$；

于是 $F*G$ 可以通过两次 $\text{FMT}$ 加一次 $\text{IFMT}$ 完成，复杂度 $O(n2^n)$。

而对于 $\text{FMT}(F\times G)$，注意到相当于在计算 $\text{FMT}(F*G)$ 的同时要求 $|X|+|Y|=|S|$，那么我们可以令 $R'=R[x]$，即 $R$ 上的多项式环，并令 $F'_S=x^{|S|}F_S$，$G'_S=x^{|S|}G_S$，则 $\text{FMT}(F\times G)_S=[x^{|S|}]\text{FMT}(F'*G')_S$。

于是 $F\times G$ 可以通过 $R[x]$ 上的两次 $\text{FMT}$，一次多项式乘法和一次 $\text{IFMT}$ 完成，复杂度 $n^22^n$。

3. 集合幂级数和形式幂级数复合

对于同样定义在 $R$ 上的正指数形式幂级数 $H(x)\in R[x]$，设其为 $H(x)=\sum\limits_{i=1}^\infin h_ix^i$。定义集合幂级数 $F$ 在 $H$ 上的复合 $H(F)$：

$H(F)=\sum\limits_{i=1}^\infin h_iF^i$

其中 $F^i$ 为 $i$ 个 $F$ 的无交并乘积。

这里假定 $F_\empty=0$，否则可能不收敛。那么显然 $i>n$ 的 $F_i$ 为全零映射，故 $H(F)=\sum\limits_{i=1}^n h_iF^i$。

考虑无交并乘积的计算过程，注意到有 $\text{FMT}(H(F))_S=\sum\limits_{i=1}^nh_i\text{FMT}(F^i)_S=\sum\limits_{i=1}^nh_i[x^{|S|}]\text{FMT}(F')^i_S$，所以可以直接 $O(n^32^n)$ 算出。

但是对于一些特殊的 $H$，例如 $\exp$ 和 $\ln$，$[x^{|S|}]\text{FMT}(F')^i_S$ 往往可以快速算出，可以做到 $O(n^22^n)$。