（暴力）多项式与生成函数_成型笔记

多项式与生成函数

由于快速傅里叶变换并不在 CCF 的考纲之内，故对于多项式的考察仅限于公式推导。

即使是只剩下公式推导，多项式仍然是一个强大的工具。

多项式暴力全家桶

以下很多东西是在 $\bmod\ x^c$ 意义下定义的，不过推导过程并不需要用到 $c$，比较神奇。

加法 数乘 卷积

暴力模拟即可。

加法复杂度 $\max(n,m)$，数乘复杂度 $n$，卷积复杂度 $nm$。

求导

$a'_i=(i+1)a_{i+1}$，注意这会丢掉常数项。

积分

$a'_i=\frac{a_{i-1}}{i}$。

求逆

其实就是 $\forall n,\sum_iA_iB_{n-i}=[n=0]$。

不妨设 $n>0$，把 $A_0$ 拿出来：

$$A_0B_n=-\sum_{i=1}^nA_iB_{n-i}\\B_n=\frac{-\sum_{i=1}^nA_iB_{n-i}}{A_0}$$

边界是 $B_0=\frac{1}{A_0}$，这也告诉我们多项式存在逆的条件是 $A_0\ne0$。

递推即可，复杂度 $\cal O(cn)$（$c$ 为模数 $x^c$ 的指数），这也告诉我们两个多项式相除复杂度必须至少是分母的平方。

多项式相除就是多计算一次卷积，复杂度 $\cal O(cn+cm)$。

实际上我们不必求逆再相乘，可以进一步求多项式除法：

$$\forall n,\sum_{i}A_i({\frac BA})_{n-i}=B_n\\A_0(\frac B A)_n=B_n-\sum_{i=1}^nA_i(\frac B A)_{n-i}\\(\frac B A)_n=\frac{B_n-\sum_{i=1}^nA_i(\frac{B}{A})_{n-i}}{A_0}$$

然后你发现这个东西就变成 $\cal O(cm)$（$m$ 为分母次数）的了，这也告诉我们多项式除单项式还是能做的。

你可能会举出退背包的例子告诉我这可以做到 $\cal O(nm)$，那岂不是求逆复杂度直接变成 $\cal O(n)$，乐。

事实上这里的退背包取决于你想要多长的数组，也就是 $c$，你至少要保证答案数组长度 $\le c$。

ln/exp

注意多项式存在 $\ln$ 的条件是 $[x^0]F(x)=1$，小时候看这集兴奋地说解决了离散对数求解难题。

多项式存在 $\exp$ 的条件是 $[x^0]F(x)=0$。

令 $G(z)=\ln F(z)$，对两边求导，得：

$$G'(z)=\frac{F'(z)}{F(z)},G(z)=\int \text{d}z\frac{F'(z)}{F(z)}$$

令 $G(z)=\exp F(z)$，两边求导，得：

$$G'(z)=G(z)F'(z)$$

展开 $F(x),G(x)$ 系数序列为 $A,B$：

$$\begin{aligned}(n+1)B_{n+1}&=\sum_{i=0}^nB_{n-i}(i+1)A_{i+1}\\B_n&=\frac 1 n\sum_{i=1}^niA_iB_{n-i}\end{aligned}$$