多项式全家桶

前置芝士：

• FTT & NTT
• 不低于高中的数学推导能力
• 不低于高中的代数芝士
• 高等数学初步
• 复变函数初步（？）

多项式乘法

目标：给定两个多项式 $F,G$，求 $F\times G$。
有 $F(x)G(x)\equiv (FG)(x)$，将 $F,G$ 转为点值形式后直接求积即可。

多项式牛顿迭代系列

目标：给定一个函数 $X$，求一个多项式 $F$，满足 $X(F(x))\equiv 0(\mathrm{mod}{x}^n)$
定义 $X(F_0(x))\equiv 0(\mathrm{mod}{x}^{n/2})$。
在 $F_0(t)$ 处对 $X(t)$ 进行泰勒展开，得到

$$X(p)\equiv \sum _{k=0}^{\mathrm{\infty }}\frac{{\mathrm{d}}^{k}X(F_0(t))}{\mathrm{d}{t}^k}(p-F_0(t){)}^k$$

，展开 $X(F(t))$（小(x)粉(f)兔(t)），得到

$$X(F(t))\equiv \sum _{k=0}^{\mathrm{\infty }}\frac{{\mathrm{d}}^{k}X(F_0(t))}{\mathrm{d}{t}^k}(F(t)-F_0(t){)}^k$$

，而这个东西 $\equiv 0$。
因为 $F(x)\equiv F_0(x)(\mathrm{mod}{x}^{n/2})$，所以有 $x^{n/2}\mid F(x)-F_0(x)$，两边平方得到 $x^n\mid (F(x)-F_0(x){)}^2$，所以在 $(\mathrm{mod}{x}^n)$ 意义下，可以只取前两项，得到准确结果，于是柿子变成

$$X(F(t))\equiv X(F_0(t))+X^{\prime }(F_0(t))\times (F(t)-F_0(t))\equiv 0$$

（$X^{\prime }$ 代表导数），因为 $X,F_0,X^{\prime }$ 都是已知，所以问题转化为一元一次方程，解得

$$F(t)\equiv F_0(t)-{\displaystyle \frac{X(F_0(t))}{X^{\prime }(F_0(t))}}$$

。

多项式倒数

我一般把多项式乘法逆叫做这名。
目标：$X(F(t))\equiv {\displaystyle \frac{1}{F(t)}}-H(t)$，其中 $H(x)$ 给定。
解：注意求导时是对 $F_0(t)$ 求导，$H(t)$ 要视为常数，得到 ${\displaystyle \frac{\partial X}{\partial F_0(t)}}\equiv -F_0^{-2}(t)$，注意这里有三个 “-” 号，计算时要小心符号：

$$F(t)\equiv F_0(t)-{\displaystyle \frac{X(F_0(t))}{X^{\prime }(F_0(t))}}\equiv F_0(t)-{\displaystyle \frac{F_0^{-1}(t)-H(t)}{-F_0^{-2}(t)}}\equiv F_0(t)+{\displaystyle \frac{F_0^{-1}(t)-H(t)}{F_0^{-2}(t)}}\equiv 2F_0(t)-H(t)F_0^2(t)$$

。

多项式 $\exp$

• 目前还没有多项式 $\ln$，所以先看后面的多项式 $\ln$。
  目标：$X(F(t))\equiv \ln F(t)-H(t)$，其中 $H(x)$ 给定。
  解：${\displaystyle \frac{\partial X}{\partial F_0(t)}}\equiv {\displaystyle \frac{1}{F_0(t)}}$，得到 $F_0(t)-{\displaystyle \frac{\ln F_0(t)-H(t)}{1/F_0(t)}}\equiv F_0(t)\times (1-\ln F_0(t)+H(t))$。
  特别地：$A^B\equiv \exp (B\ln A)$

多项式 $\ln$

目标：给定一个 $H(x)$，求 $\ln H(x)$
有 $\ln H(x)\equiv F(x)$，两边求导 ${\displaystyle \frac{H^{\prime }(x)}{H(x)}}\equiv F^{\prime }(x)$，有

$$F(x)\equiv \int {\displaystyle \frac{H^{\prime }(x)}{H(x)}}\mathrm{d}x$$

，其中，分母的 $H(x)$ 可以使用多项式倒数求出。

多项式带余除法

目标：给定一个 $F(x),G(x)$，求 $FmodG,(F-FmodG)/G$。
有 $F(x)\equiv G(x)H(x)+L(x)$，同时记 $m\equiv \mathrm{deg}G+1$。
换元法：$u\to x^{-1}$，发现

$$x^{n}F({\displaystyle \frac{1}{x}})\equiv \sum _{i\equiv 0}^{n-1}{F}_{n-1-i}{x}^i\equiv Fi(x)$$

，简单代数运算可得 $Fi(x)\equiv Gi(x)Hi(x)+x^{n-m+1}Li(x)$，在 $(\mathrm{mod}{x}^{n-m+1})$ 意义下就是多项式除法，而且正好 $H$ 是 $(n-1)-(m-1)\equiv n-m$ 次，在 $(\mathrm{mod}{x}^{n-m+1})$ 下完完全全就没有精度损失，于是 $L(x)\equiv F(x)-G(x)H(x)$。

多项式三角函数

多项式 $\sin$

因为 $e^{ix}=\cos x+i\sin x$，因为 $\cos$ 是偶函数，$\sin$ 是奇函数得到 $e^{-ix}=\cos x-i\sin x$，两个式子相减有 $e^{ix}-e^{-ix}=2i\sin x$，有 $\sin x={\displaystyle \frac{e^{ix}-e^{-ix}}{2i}}$，而 $i\equiv {\omega }_4$，正好 $4\equiv 2^2$，可以 NTT。于是只要 多项式 $\exp$ 即可。

多项式 $\cos$

如 $\sin$ 提到的两个式子相加有 $e^{ix}+e^{-ix}=2\cos x$，有 $\cos x={\displaystyle \frac{e^{ix}+e^{-ix}}{2}}$，类似处理即可。

多项式 $\tan$

有 $\tan F(x)={\displaystyle \frac{\sin F(x)}{\cos F(x)}}$。

多项式反三角函数

带入牛顿迭代即可。
这里只给结论：
${\sin }^{-1}F(t)\equiv F_0(t)-\tan F_0(t)+{\displaystyle \frac{H(p)}{\cos F_0(t)}}$
${\cos }^{-1}F(t)\equiv F_0(t)+{\displaystyle \frac{\cos F_0(t)-H(t)}{\sin F_0(t)}}$
${\tan }^{-1}F(t)\equiv F_0(t)-\sin F_0(t)\times \cos F_0(t)+H(t){\cos }^2{F}_0(t)$