多项式对数函数、指数函数和欧拉变换

与一般想法不同，多项式也有自己的对数函数和指数函数。它们也可以在 $O(n\log n)$ 的优秀时间内求解。

有这么一个式子广为人知

$$e^x=\sum\limits_{i=0}^{+\infty}\dfrac{x^i}{i!}$$

事实上对数函数也可以像这样用无限幂级数定义：

$$\ln(1-x)=-\sum\limits_{i=1}^{+\infty}\dfrac{x^i}{i}$$

$$\ln(1+x)=-\sum\limits_{i=1}^{+\infty}\dfrac{(-1)^i\cdot x^i}{i}$$

它们就是大名鼎鼎的泰勒级数。指数函数的泰勒展开式对于任意实数 $x$ 都成立，对数函数的泰勒展开式只对定义域内的一些 $x$ 成立；不过我们并不关心 $x$，只关心其系数。多项式的指数函数和对数函数就是用这些级数定义的。因为这些级数都是无限级数，多项式只在模意义下存在指数函数和对数函数。

多项式对数函数

多项式 $g(x)$ 在模 $x^n$ 意义下的对数函数存在，当且仅当其常数项为 $1$，否则它对应的泰勒级数不收敛。把 $\ln g(x)$ 视作一个关于 $x$ 的函数，我们有

$$\begin{aligned}\left[\ln g(x)\right]^\prime=\dfrac{g(x)^\prime}{g(x)}\\ \ln g(x)=\int\mathrm{d}\ln g(x)=\int\dfrac{g(x)^\prime}{g(x)}\mathrm{d}x\end{aligned}$$

只要对 $g(x)$ 求导，再乘上 $\dfrac{1}{g(x)}$ 就能够得到 $\ln g(x)$ 的导数，这个导数的积分就是 $\ln(g(x))$。多项式求导、积分都是非常容易的事情，但是，$\dfrac{g(x)^\prime}{g(x)}$ 的不定积分随常数项的不同有无穷多个，我们应该取哪一个呢？我们取常数项为 $0$ 的那个作为答案，因为只有常数项为 $0$ 的多项式在模意义下存在指数函数。

多项式指数函数

上面我们提到，多项式 $g(x)$ 在模 $x^n$ 意义下的指数函数存在，当且仅当其常数项为 $0$，否则它对应的泰勒级数也一样不收敛。由于 $\exp f(x)$ 的导数里还是存在 $\exp f(x)$，我们只能用分治 FFT 的方法 $O\left(n\log^2n\right)$ 求出。这种方法由于比较缓慢而不常使用，通常我们使用 Newton's Method $O(n\log n)$ 求。

分治法并非一无是处。这个方法不需要写多项式求逆和多项式对数函数，写起来要快很多；虽然复杂度多一个对数，但常数较小，也不会慢特别多。

多项式的指数函数是有实际的组合意义的。设 $f(x)$ 是一个大小为 $i$ 的盒子内部分配方案数的指数型生成函数（即，$[\dfrac{x^i}{i!}]f(x)$ 表示一个盒子装 $i$ 个小球的方案数），则 $\exp f(x)$ 表示 $i$ 个有标号小球分配到任意多个无标号盒子的方案数的指数型生成函数（即，$[\dfrac{x^i}{i!}](\exp f(x))$ 表示 $i$ 个相互区分的小球放到若干个完全一样的盒子的方案数）。这个组合意义与指数函数的幂级数有关系。

这一点的证明只需用下式说明

$$\exp f(x)=\sum\dfrac{f^i(x)}{i!}=\prod \exp f_ix^i$$

其中的含义是：

$f^i(x)$ 是将有标号小球分配到 $i$ 个有标号盒子的方案数的指数型生成函数；

$\dfrac{f^i(x)}{i!}$ 是将有标号小球分配到 $i$ 个无标号盒子的方案数的指数型生成函数；

$\sum\dfrac{f^i(x)}{i!}$ 是将有标号小球分配到任意多个无标号盒子的方案数的指数型生成函数；

$\prod \exp f_ix^i$ 的含义请自行思考。

欧拉变换

在多项式指数函数中，我们提到了多项式指数函数的组合含义。如果要求无标号小球放到无标号盒子的方案数，我们应该怎么做呢？

令 $f(x)=\sum\limits_{i=1}^nf_ix^i$，则我们可以写出所求的普通型生成函数 $g(f(x))$

$$g(f(x))=\prod\limits_{i=1}^n\dfrac{1}{(1-x^i)^{f_i}}$$

注意

在指数函数的组合意义中，我们使用了指数型生成函数（EGF），而在欧拉变换中，我们使用的却是普通型生成函数（OGF）。

出现了 $1-x^k$，对此敏感的我们考虑求出它的对数函数

$$\ln g(f(x))=\sum\limits_{i=1}^nf_i\sum\limits_{j=1}^{+\infty}\dfrac{x^{ij}}{j}$$

交换求和顺序

$$\begin{aligned}\ln g(f(x))&=\sum\limits_{i=1}^{+\infty}\dfrac{1}{i}\sum\limits_{j=1}^{n}f_jx^{ij}\\&=\sum\limits_{i=1}^{+\infty}\dfrac{f(x^i)}{i}\end{aligned}$$

于是

$$g(f(x))=\exp \sum\limits_{i=1}^{+\infty}\dfrac{f(x^i)}{i}$$

我们把 $g(f(x))$ 称作 $f(x)$ 的欧拉变换，它的组合含义是无标号小球放到无标号盒子的方案数。我们可以用 $O(n\log n)$ 的复杂度求一个多项式 $f(x)$ 的欧拉变换。

付公主的背包 的另一种解释

付公主的背包可以用欧拉变换解释。完全背包的本质就是把 $s$ 个无标号体积放到 $n$ 种有标号商品中。

评论