多项式专题
多项式操作很有用，写一下。
现学现写的，代码鸽了。
前置知识
多项式乘法(FFT)：分治里有
多项式除法和取模概念
对于一个多项式 $A(x),B(x)$ 来说，存在有唯一的 $Q(x),R(x)$ 满足：
$$ A(x) = Q(x)B(x) + R(x) $$
其中保证 $R(x)$ 的最高次项小于 $B(x)$ 的，那么我们称 $Q(x)$ 为 $B(x)$ 除 $A(x)$ 的商，$R(x)$ 为其除数。
于是乎，我们可以把同余的那一套理论照搬过来，搞一个多项式的同余系。
多项式求逆
这个求逆是在 $mod \ x^n$ 下进行的，即对于一个多项式 $A(x)$，如果存在一个多项式 $B(x)$，使得
$$A(x)B(x) \equiv 1 \pmod {x^n}$$
那么我们称 $B(x)$ 为 $A(x)$ 的逆，记作$A^{-1}(x)$。
容易证明，一个多项式是否存在逆完全取决于其常数项是否存在逆。
那么如何求一个多项式的逆呢？
因为是多项式，所以我们采用分治的方法去进行求解 (铁逻辑)。
我们考虑我们已经求出了在 $\pmod {x^{\lceil\frac n2\rceil}}$ 下的逆 $B’(x)$，那么有
$$ A(x)B’(x) \equiv 1 \pmod {x^{\lceil\frac n2\rceil}} $$
根据条件，我们有
$$ A(x)B(x) \equiv 1 \pmod {x^{\lceil\frac n2\rceil}} $$
两式相减，我们得到
$$ B(x) - B’(x) \equiv 0 \pmod {x^{\lceil\frac n2\rceil}} $$
因为 $A(x)$ 不一定同余 $0$，所以这个式子成立一定要保证后者同余 $0$。
我们将其平方得：
$$ B(x)^2 - 2B(x)B’(x) + B’(x)^2 \equiv 0 \pmod {x^n} $$
仔细思考一下平方后似乎确实在模 $x^n$ 下为 $0$.
两边乘上 $A(x)$，我们又有 $A(x)B(x) \equiv 1 \pmod {x^n}$，得：
$$ B(x) \equiv 2B’(x) - A(x)B’(x)^2 \pmod {x^n} $$
那么我们最终复杂度就是 $T(n) = T(\frac n2) + O(n\log n) = O(n\log n)$
这个东西我们可以用来处理一些不好展开的生成函数。
多项式除法和取模实现
一个非常 NB 的算法，我们来学习一下。
首先，我们给定一个最高次项为 $n$ 的多项式 $A(x)$，并且定义
$$ A^R(x) = x^nA(\frac 1x)$$
即将 $A(x)$ 的系数反转，如 $1 + 2x + 3x^2$ 会变成 $3 + 2x + x^2$。
接下来我们进行非常神奇的一个操作，我们设
$$ A(x) = D(x)B(x) + R(x) $$，其中 $R(x)$ 的最高次幂小于 $B(x)$ 的最高次幂。即 $D(x)$ 为除数，$B(x)$ 为商，$R(x)$ 为余数。
补充：其中 $B(x)$ 的最高次幂为 $m$。
那么我们用 $\frac 1x$ 替换等式中的 $x$ 并在等式两边都乘上 $x^n$，有
$$ x^nA(\frac 1x) = x^{n - m}D(\frac 1x)x^mB(\frac 1x) + x^{n - m + 1}x^{m - 1}R(x) $$
$$ A^R(x) = D^R(x)B^R(x) + x^{n - m + 1}R^R(x) $$
我们发现 $D(x)$ 的最高次幂无非最多就是 $n - m$，而 $x^{n - m + 1}R^R(x)$ 的最低次幂一定高于 $n - m$，于是我们将这个式子放在模 $x^{n - m + 1}$ 的同余系下，得到：
$$ A^R(x) \equiv D^R(x)B^R(x) \pmod{x^{n - m + 1}} $$
于是乎，我们只要是求出 $B^R(x)$ 在模 $x^{n - m + 1}$ 下的逆元就能求出 $B^R(x)$，继而求出 $B(x)$，然后反代出 $R(x)$。
最终时间复杂度依然为 $O(n\log n)$
多项式的多点求值和快速插值
多项式的多点求值
首先考虑多点求值，即对于给定的一个多项式 $A(x)$ 和一个含有 $n$ 个元素的集合 $S$，对于集合中的所有元素，求 $A(s) \ (s \in S)$。
朴素的代入求值是 $O(n^2)$ 的，时间复杂度太高，我们这里考虑一种基于分治的解决方法。
首先我们考虑把集合 $S = {a_1,\dots,a_n}$ 分为两个集合 $S_0$，$S_1$，每一个集合都拥有 $S$ 中一半的元素，那么我们接下来考虑如何将这个问题分为两个次数减半的多项式。
我们设
$$ P_0(x) = \prod_{i = 1}^{\lfloor\frac n2\rfloor}(x - a_i) $$
那么我们再设
$$ A(x) = D(x)P_0(x) + A_0(x) $$
我们发现，再这种情况下，我们只要是求出将前一半的数代入 $A_0(x)$ 的结果即可，即 $A(x)$ 对 $P_0(x)$ 取模的结果，对于 $S_1$ 集合的部分我们作的相同的处理，这样我们就把一个问题分成了两个子问题，最终时间复杂度 $O(n \log^2 n)$。
多项式的快速插值
好了，我们已经回了多项式的多点求值了，我们可以在此基础上探究多项式的快速插值了。
朴素的拉格朗日插值法的时间复杂度是 $O(n^2)$ 的，这里，我们依然是基于分治的思想来进行快速插值。
设我们当前需要插值的点集为 $S$，其中 $S = {(x_i,y_i)},i = 0,\dots,n$。
我们的目的是搞出来一个最高次数为 $n$ 的多项式 $A(x)$ 使得 $A(x_i) = y_i$。
我们依然是把点集平分为两部分，对应的集合为 $S_0$，$S_1$。
那么我们首先对于 $S_0$ 进行插值，设求出来的多项式为 $A_0(x)$。
并且设
$$P(x) = \prod_{i = 1}^{\lfloor\frac n2\rfloor}(x - a_i)$$
我们再设 $A(x) = A_1(x)P(x) + A_0(x)$。
这个 $A(x)$ 已经满足对于 $0 \leq i \leq \lfloor \frac n2 \rfloor$，$A(x_i) = y_i$ 了。
我们知道，$A(x)$ 还要对后一半满足，也就是对于 $\lfloor \frac n2 \rfloor + 1 \leq i \leq n$，$y_i = A(x_i) = A_1(x_i)P(x_i) + A_0(x_i)$。
即满足
$$ A_1(x_i) = \frac{y_i - A_0(x_i)}{P(x_i)} $$
我们通过递归插值把 $A_1(x)$ 插出来即可。
最终时间复杂度 $O(n \log^2n)$。
这里原博客好像说的是 $O(n \log^3n)$，我感觉多一次，到时候写出来代码再看吧。
多项式上牛顿迭代的应用
鸽了，待续。