集合幂级数

对于两个集合幂级数 \(f\) 和 \(g\) ，定义其和 \(h\) ：

\[ h_S = f_S + g_S \]

对于两个集合幂级数 \(f\) 和 \(g\) ，定义其乘积 \(h\) ：

\[ h_S = \sum_{T \subseteq S} f_T \times g_{S \setminus T} \]

即常说的子集卷积。

那么定义了乘法和加法，就能进一步定义更多运算。

在这之前先引入集合占位幂级数。

集合占位幂级数

对于集合幂级数 \(f\) ，其占位幂级数 \(P(f)\) 的每一位实际是一个多项式，满足：

\[ P(f)_S = f_S x^{|S|} \pmod{x^{|S|+1}} \]

有了占位幂级数，就可以很容易地把集合幂级数的乘法转换为并卷积，即通过莫比乌斯变换可以很好处理两个集合幂级数的乘法。

具体的，对于集合幂级数 \(f\) 和 \(g\) ，求出幂级数 \(p\) 满足：

\[ P(h)_S = \sum_{A \cup B = S} P(f)_A \times P(g)_B \]

其中 \(P(f)_A \times P(g)_B\) 就是多项式卷积。

那么根据集合并卷积的性质可以知道：

\[ FMT(P(h))_S = FMT(P(f))_S \times FMT(P(g))_S \]

update: 这里的“等于”并不是严格意义上的等于，而是一种整体上的等价。

暴力进行多项式卷积，一次乘法的复杂度为 \(O(2^n n^2)\) ，其中 \(n\) 是全集的大小。

求逆

对于集合幂级数 \(f\) ，定义其逆元 \(g\) 为满足 \(f \times g = e\) 的集合幂级数。

其中 \(e\) 是集合幂级数的单位元，满足 \(\forall f, f \times e = f\) 。

可以知道 \(\forall S, FMT(P(e))_S = 1\) 。

那么就有 \(\forall S, FMT(P(g))_S = FMT(P(f))_S^{-1} \pmod{x^{|S|+1}}\) 。

暴力多项式求逆，复杂度 \(O(2^n n^2)\) ，其中 \(n\) 是全集的大小。

开根

对于集合幂级数 \(f\) ，定义其平方根 \(g\) 为满足 \(g \times g = f\) 的集合幂级数。

可以知道 \(\forall S, FMT(P(g))_S^2 = FMT(P(f))_S \pmod{x^{|S|+1}}\) 。

暴力多项式开根，复杂度 \(O(2^n n^2)\) ，其中 \(n\) 是全集的大小。

其他

类似的也可以定义 \(\exp\) 和 \(\ln\) 。

update: exp 的定义可以利用泰勒展开式：\(e^A = \sum_{i\ge{0}} \frac{A^i}{i!}\) ，对应的可以定义 ln 。

不难发现所有集合幂级数的运算都可以转换莫比乌斯变换后占位幂级数的多项式运算。

暴力做多项式运算，复杂度都是 \(O(2^n n^2)\) ，理论上可以做到 \(O(2^n n \log n)\) 。

但是考虑到对占位幂级数做莫比乌斯变换的复杂度就要 \(O(2^n n^2)\) 。 且由于集合幂级数运算的运算的瓶颈主要在于 \(O(2^n)\) ，\(n\) 往往很小。 此时 \(O(n \log n)\) 的多项式运算带来的常数因子影响是很大的，因此集合幂级数的运算往往使用 \(O(n^2)\) 的暴力运算。