杂谈

艾玛这篇文章是6月份创建的……然后一直坑在这里。
等UR#3结束之后，这东西应该也烂大街了吧（其实现在也烂大街了）。
那么我就稍微介绍一下吧。
由于这里面的内容我大(quan)都(bu)没有实现，早已沦为了嘴巴选手，所以有问题的内容请及时告知我，我再修改。
如果你想拿去出题……常数问题自己考虑吧……

问题

给出多项式 $G(x)$，求解多项式 $F(x)$，满足：

$$G(F(x)) \equiv 0 \bmod{x^n}$$

你只需要给出 $F(x) \bmod{x^n}$ 即可。

解法

首先先不要抱太大希望……这个问题我也没有得到足够好的复杂度。所以大家大可放心不会非常毒瘤地祸害到各位。
思路大概还是利用多项式求逆那样地倍增。
不妨假设我们有：

$$G(F_t(x)) \equiv 0 (\bmod{x^{2^t})}$$

先奠基，显然，F(x)的常数项必然为0，否则无法在模意义下收敛。
现在我们试图将它扩展到模 $x^{2^{t+1}}$ 意义下。
对 $G(F_{t+1}(x))$ 进行在 $F_t(x)$ 上进行泰勒展开（这一步的正确性可以直接通过泰勒公式的推导说明）。

$$G(F_{t+1}(x))=G(F_t(x))+\frac{G'(F_t(x))}{1!}(F_{t+1}(x)-F_t(x))^1+\frac{G''(F_t(x))}{2!}(F_{t+1}(x)-F_t(x))^2+\cdots$$

注意到 $\deg (F_{t+1}(x)-F_t(x))^2 \geq 2^{t+1}$，那么从第三项开始，后面的项在模 $2^{t+1}$ 后均为0.
故我们有：

$$\begin{eqnarray} G(F_{t+1}(x)) & \equiv & G(F_t(x))+G'(F_t(x))*(F_{t+1}(x)-F_t(x)) & (\bmod{x^{2^{t+1}}}) \\ F_{t+1}(x) & \equiv & F_t(x) - \frac{G(F_t(x))}{G'(F_t(x))} & (\bmod{x^{2^{t+1}}}) \end{eqnarray}$$

根据迭代式，我们就可以在 $O(1)$ 的附加时间内计算出 $F_k(x)$ 了。
不妨设我们计算 $G(F(x)) \bmod{x^n}$ 的复杂度为 $C(n)$，根据多项式除法的复杂度分析，总复杂度为即为 $O(C(n))$。
那么怎么计算这个多项式嵌套呢，我查到的最好的复杂度是 $O((n \log n)^{1.5})$ 的，将另写一篇博客介绍。如果你问我这能出到什么数据范围，我猜，能跑出 $n=20000$ 吧……
有人觉得这可能没什么实际的用处，但是事实上我们的复杂度就卡在这个多项式嵌套上，如果我们可以根据题目的特殊性来解决这个问题，那么仍不失为一个好方法。
接下来看一看几个应用吧！

应用

多项式求逆

问题

即对于给出的多项式 $P(x)$，要求 $F(x)$，满足：

$$F(x) * P(x) - 1 = 0 (\bmod{x^n})$$

解法

将 $F(x)$ 视作变量，我们可以非常快地得到迭代式：

$$\begin{eqnarray} F_{t+1}(x) & \equiv & F_t(x) - \frac{F_t(x)*P(x)-1}{P(x)} & (\bmod{x^{2^{t+1}}}) \\ & \equiv & F_t(x) - (F_t(x)*P(x)-1)*F_t{x} & (\bmod{x^{2^{t+1}}}) \\ & \equiv & F_t(x)*F_t(x)*P(x)+2*F_t{x} & (\bmod{x^{2^{t+1}}}) \end{eqnarray}$$

有没有觉得很眼熟？对了，这就是我们在多项式求逆中得到的式子。

多项式开方

同样的，多项式开方也可以迎刃而解。

问题

即对于给出的多项式 $P(x)$，要求 $F(x)$，满足：

$$F(x) * F(x) - P(x) = 0 (\bmod{x^n})$$

解法

同样地推出递推式：

$$\begin{eqnarray} F_{t+1}(x) & \equiv & F_t(x) - \frac{F_t(x)*F_t(x)*P(x)}{2*F_t(x)} & (\bmod{x^{2^{t+1}}}) \\ \end{eqnarray}$$

问题得到了解决。

多项式求指数函数

问题

对于给出的多项式 $P(x)$，要求 $F(x)$，满足：

$$e^{P(x)} - F(x) = 0 (\bmod{x^n})$$

解法

由于常数项我们不知道，故需要对所求式进行一定变形：

$$\ln F(x) - P(x) = 0 (\bmod{x^n})$$

同样地推出递推式：

$$\begin{eqnarray} F_{t+1}(x) & \equiv & F_t(x) - (\ln F_t(x)-P(x))*F_t(x) & (\bmod{x^{2^{t+1}}}) \\ \end{eqnarray}$$

需要求 $\ln F(x)$，仍然需要一些数学技巧：

$$\ln F(x) = \int \frac{F'(x)}{F(x)} dx$$

注意到对于多项式的求导和积分，都是很容易完成的，所以我们可以在 $O(n \log n)$ 时间内计算 $\ln F(x)$.
由前所述，计算 $e^{P(x)}$ 也可以在 $O(n \log n)$ 时间内完成。
从此，我们也可以推出来多项式的三角函数的求法。

多项式三角函数

问题

对于给出的多项式 $P(x)$，要求 $X(x),Y(x)$，满足：

$$\cos P(x) - X(x) \equiv 0 (\bmod{x^n}) \\ \sin P(x) - Y(x) \equiv 0 (\bmod{x^n})$$

解法

由欧拉公式可得：

$$e^{iF(x)} = \cos F(x) + i\sin F(x)$$

我们只需要用复数来做即可。模意义下，我们可以用二元组来模拟复数运算。
至此，我们已经可以在 $O( n \log n )$ 时间内完成所有多项式的初等函数运算。

多项式快速幂

问题

对于给出的多项式 $P(x)$，要求 $F(x)$，满足：

$$F(x) - P(x)^k \equiv 0 (\bmod{x^{n}})$$

解法

方法学习自jiry_2！原地址：jry的博客！
稍微进行数学变换：

$$\ln F(x) - k \ln P(x) = 0$$

然后好像就做完了？
复杂度 $O(n \log n)$.

结语

絮絮叨叨了这么多，发现讲完这个东西之后，FFT系列教程没有啥好写的了？有一点忧伤……说不定以后我还会有一点别的东西分享一下吧。
感谢所有能看到这里的人（肯定是真·大神了……）。
还有一些牛顿迭代的有意思的应用，比如UR#3的微分方程什么的，我会看心(shui)情(ping)来更新的>_<~