多项式小记

· · 算法·理论

板子在此

推荐学习顺序

  1. 卷积（FFT）

  2. 卷积（NTT）

  3. 多项式求逆

  4. 多项式 \ln

  5. 多项式 \exp

  6. 多项式开根

  7. 多项式快速幂

  8. 多项式三角函数

  9. 多项式反三角函数

1 和 2 是小学内容就不讲了。

3.多项式求逆

设

F\ast G_0\equiv1\pmod{x^n} F\ast G_1\equiv1\pmod{x^{\left\lceil\frac n2\right\rceil}}

那么

F\ast G_0\equiv1\pmod{x^{\left\lceil\frac n2\right\rceil}} G_0\equiv G_1\pmod{x^{\left\lceil\frac n2\right\rceil}} G_0-G_1\equiv0\pmod{x^{\left\lceil\frac n2\right\rceil}} G_0^2+G_1^2-2G_0G_1\equiv0\pmod{x^n} G_0^2\equiv2G_0G_1-G_1^2\pmod{x^n}

两侧同时乘 F，得到关于 G 的递推式

G_0\equiv G_1(2-FG_1)\pmod{x^n}

递归计算即可，边界 n=1 时有 G(x)=[x^0]F(x)^{-1}。

4.多项式 \ln

当且仅当 [x^0]F(x)=1 时，\ln F(x)\bmod{x^n} 存在。

易得

\ln F(x)\equiv\int\dfrac{F'(x)}{F(x)}\text dx\pmod{x^n}

求导和积分：

F'(x)=\sum\limits_{i=1}^na_ix^{i-1} \int F(x)\text dx=\sum\limits_{i=0}^n\dfrac{a_ix^{i+1}}{i+1}+C

5.多项式 \exp

当且仅当 [x^0]F(x)=0 时，\exp F(x)\bmod{x^n} 存在。

构造 G(x)，并要求 F(x) 使得 G(F(x))\equiv0\pmod{x^n}。

若现在已经求出

G(F_0(x))\equiv0\pmod{x^{\left\lceil\frac n2\right\rceil}}

将 G(F(x)) 进行泰勒展开

\begin{aligned} G(F(x))&=G(F_0(x))\\ &+\dfrac{G'(F_0(x))}{1!}(F(x)-F_0(x))\\ &+\dfrac{G''(F_0(x))}{2!}(F(x)-F_0(x))^2\\ &+\cdots \end{aligned}

令

G(x)\equiv e^{F(x)}\pmod{x^n}

由于 F(x)\equiv F_0(x)\pmod{x^{\left\lceil\frac n2\right\rceil}}，泰勒展开仅需保留前两项。

G(x)\equiv e^{F_0(x)}\pmod{x^{\left\lceil\frac n2\right\rceil}}

变形后有

\ln G(x)-F(x)\equiv0\pmod{x^n}

构造函数 A(G(x))=\ln G(x)-F(x)，那么 A'(G(x))=\dfrac1{G(x)}，可得到关于 G(x) 的递推式

\begin{aligned} G(x)&\equiv G_0(x)-\dfrac{A(G_0(x))}{A'(G_0(x))}\\ &\equiv G_0(x)(1-\ln G_0(x)+F(x))\pmod{x^n} \end{aligned}

递归计算即可，边界 n=1 时有 G_0(x)=1。

6.多项式开根

设

G_0^2(x)\equiv F(x)\pmod{x^n} G_1^2(x)\equiv F(x)\pmod{x^{\left\lceil\frac n2\right\rceil}}

有

G_0(x)-G_1(x)\equiv0\pmod{x^{\left\lceil\frac n2\right\rceil}} G_0^2(x)+G_1^2(x)-2(G_0\ast G_1)(x)\equiv0\pmod{x^n} F(x)+G_1^2(x)-2(G_0\ast G_1)(x)\equiv0\pmod{x^n} G_0(x)\equiv\dfrac{F(x)+G_1^2(x)}{2G_1(x)}\pmod{x^n}

递归计算即可，边界 n=1 时有 G_0(x)\equiv\sqrt{[x^0]F(x)}\pmod p，跑一次二次剩余即可求出。

7.多项式快速幂

F^k(x)=\exp k\ln F(x)

也可以使用类似对数字进行快速幂的方法完成，时间为 O(n\log^2n)。

8.多项式三角函数

由欧拉恒等式有

\text e^{\text ix}=\cos x+\text i\sin x \text e^{-\text ix}=\dfrac1{\text e^{\text ix}}=\cos x-\text i\sin x

相加相减得到

2\text i\sin x=\text e^{\text ix}-\text e^{-\text ix} 2\cos x=\text e^{\text ix}+\text e^{-\text ix}

代入 x=F(x) 即得

\sin F(x)=\dfrac{\text e^{\text iF(x)}-\text e^{-\text iF(x)}}{2\text i} \cos F(x)=\dfrac{\text e^{\text iF(x)}+\text e^{-\text iF(x)}}2 \tan F(x)=\dfrac{\sin F(x)}{\cos F(x)}=\dfrac{\dfrac{\text e^{\text iF(x)}-\text e^{-\text iF(x)}}{2\text i}}{\dfrac{\text e^{\text iF(x)}+\text e^{-\text iF(x)}}2}=\dfrac{\text e^{\text iF(x)}-\text e^{-\text iF(x)}}{\text i(\text e^{\text iF(x)}+\text e^{-\text iF(x)})}

至于 \text i\bmod p 怎么求，显然 \text i=\omega_4^1，于是 \text i\equiv g^\frac{(p-1)}4\pmod p。

因此可用一次多项式 \exp 得到 \text e^{\text iF(x)}，一次多项式求逆得到 \text e^{-\text iF(x)}。

9.多项式反三角函数

\begin{aligned} &\arcsin F(x)\\ =&\int\text d(\arcsin F(x))\\ =&\int(\arcsin F(x))'\text dx\\ =&\int\dfrac{F'}{\sqrt{1-F^2}}\text dx\\ \end{aligned} \begin{aligned} &\arccos F(x)\\ =&\int\text d(\arccos F(x))\\ =&\int(\arccos F(x))'\text dx\\ =&-\int\dfrac{F'}{\sqrt{1-F^2}}\text dx\\ \end{aligned} \begin{aligned} &\arctan F(x)\\ =&\int\text d(\arctan F(x))\\ =&\int(\arctan F(x))'\text dx\\ =&\int\dfrac{F'}{1+F^2}\text dx\\ \end{aligned}