1.2.2 [学习笔记]集合幂级数初步

Ln 与 Exp

既然能做子集卷积，那么也理应能对集合幂级数做一系列形式幂级数上对应的操作。

考虑先前的子集卷积做法，实际上是，我们添加了一个维度来记录集合的大小，即通过占位多项式区分出了应当溢出的值，对原来维度每个值逐次作莫比乌斯变换，再对占位多项式的一维作形式幂级数操作。

同样的，集合幂级数的 Ln 与 Exp 就是这么做的。

但我们肯定不会写那个 FFT 的，常数也太爆了。

我们知道 \(G=\exp-1\) 满足

\[ G'=F'\exp(F) \]

提取第 \(n-1\) 项系数有

\[ g_n=\frac{1}{n}\sum_{i=1}^{n-1}if_{i}g_{n-i} \]

那对这个变化一下式子可以得到它的逆变换 \(\ln\)，即

\[ g_n=f_n-\frac{1}{n}\sum_{i=1}^{n}ig_if_{n-i} \]