多项式全家桶

2022 年 9 月 5 日
筆記

前置芝士：

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(p) \equiv \sum_{k=0}^\infty \frac{{\rm d}^kX(F_0(t))}{{\rm d}t^k}(p-F_0(t))^k
\]

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

\[X(F(t)) \equiv \sum_{k=0}^\infty \frac{{\rm d}^kX(F_0(t))}{{\rm d}t^k}(F(t)-F_0(t))^k
\]

，而这个东西 \(\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(F(t)) \equiv X(F_0(t)) + X'(F_0(t)) \times (F(t) – F_0(t)) \equiv 0
\]

（\(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)\)，注意这里有三个 “-” 号，计算时要小心符号：

\[F(t) \equiv F_0(t) – \dfrac{X(F_0(t))}{X'(F_0(t))} \equiv F_0(t) – \dfrac{F_0^{-1}(t) – H(t)}{- F_0^{-2}(t)} \equiv F_0(t) + \dfrac{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)\) 给定。
解：\(\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)\)，有

\[F(x) \equiv \int \dfrac{H'(x)}{H(x)} {\rm d}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}\)，发现

\[x^n F(\dfrac 1x) \equiv \sum_{i\equiv0}^{n-1} F_{n-1-i}x^i \equiv Fi(x)
\]

，简单代数运算可得 \(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)\)