前置芝士：
- FTT & NTT
- 不低于高中的数学推导能力
- 不低于高中的代数芝士
- 高等数学初步
- 复变函数初步（？）
多项式乘法
目标：给定两个多项式 \(F,G\)，求 \(F \times G\)。
有 \(F(x)G(x) \equiv (FG)(x)\)，将 \(F,G\) 转为点值形式后直接求积即可。
多项式牛顿迭代系列
目标：给定一个函数 \(X\)，求一个多项式 \(F\)，满足 \(X(F(x)) \equiv 0 \pmod {x^n}\)
定义 \(X(F_0(x)) \equiv 0 \pmod{x^{n/2}}\)。
在 \(F_0(t)\) 处对 \(X(t)\) 进行泰勒展开，得到
，展开 \(X(F(t))\)（小(x)粉(f)兔(t)），得到
，而这个东西 \(\equiv 0\)。
因为 \(F(x) \equiv F_0(x) \pmod{x^{n/2}}\)，所以有 \(x^{n/2} \mid F(x) - F_0(x)\)，两边平方得到 \(x^n \mid (F(x)-F_0(x))^2\)，所以在 \(\pmod {x^{n}}\) 意义下，可以只取前两项，得到准确结果，于是柿子变成
（\(X'\) 代表导数），因为 \(X,F_0,X'\) 都是已知，所以问题转化为一元一次方程，解得
\[F(t) \equiv F_0(t) - \dfrac{X(F_0(t))}{X'(F_0(t))} \]。
多项式倒数
我一般把多项式乘法逆叫做这名。
目标：\(X(F(t)) \equiv \dfrac 1{F(t)} - H(t)\)，其中 \(H(x)\) 给定。
解：注意求导时是对 \(F_0(t)\) 求导，\(H(t)\) 要视为常数，得到 \(\dfrac{\partial X}{\partial F_0(t)} \equiv - F_0^{-2}(t)\)，注意这里有三个 “-” 号，计算时要小心符号：
。
多项式 \(\exp\)
- 目前还没有多项式 \(\ln\)，所以先看后面的多项式 \(\ln\)。
目标：\(X(F(t)) \equiv \ln F(t) - H(t)\)，其中 \(H(x)\) 给定。
解：\(\dfrac{\partial X}{\partial F_0(t)} \equiv \dfrac 1{F_0(t)}\)，得到 \(F_0(t) - \dfrac{\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)\)，两边求导 \(\dfrac{H'(x)}{H(x)} \equiv F'(x)\)，有
，其中，分母的 \(H(x)\) 可以使用多项式倒数求出。
多项式带余除法
目标：给定一个 \(F(x), G(x)\)，求 \(F \bmod G, (F - F \bmod G) / G\)。
有 \(F(x) \equiv G(x) H(x) + L(x)\)，同时记 \(m \equiv \deg G + 1\)。
换元法：\(u \to x^{-1}\)，发现
，简单代数运算可得 \(Fi(x) \equiv Gi(x) Hi(x) + x^{n-m+1} Li(x)\)，在 \(\pmod {x^{n-m+1}}\) 意义下就是多项式除法，而且正好 \(H\) 是 \((n-1)-(m-1) \equiv n-m\) 次，在 \(\pmod {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 = \dfrac{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 = \dfrac{e^{ix} + e^{-ix}}{2}\)，类似处理即可。
多项式 \(\tan\)
有 \(\tan F(x)=\dfrac{\sin F(x)}{\cos F(x)}\)。
多项式反三角函数
带入牛顿迭代即可。
这里只给结论：
\(\sin^{-1} F(t) \equiv F_0(t) - \tan F_0(t) + \dfrac{H(p)}{\cos F_0(t)}\)
\(\cos^{-1} F(t) \equiv F_0(t) + \dfrac{\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)\)