警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「学习笔记」多项式 - 数学 (咕咕咕)

简介

这篇 Blog 会介绍一些常见的多项式算法。

如果本蒟蒻咕了请在评论区提醒我,谢谢~

Todo List

  • 多项式乘法
  • 多项式求逆
  • 多项式除法
  • 多项式开根
  • 多项式求导、积分
  • 多项式多点求值
  • 多项式快速插值
  • 多项式快速幂
  • 多项式 ln
  • 多项式 exp
  • 分治 FFT
  • 多项式三角函数
  • 多项式反三角函数

多项式乘法

详见 「算法」FFT - 数学

多项式求逆

考虑倍增求解。

首先我们令原多项式为 \(F(x)\),逆元为 \(G(x)\)

假设我们已经求出了 \(\bmod x^{\lceil n/2\rceil}\) 意义下的逆元 \(H(x)\),那么显然 \(F(x)H(x) \equiv 1 \pmod{x^{\lceil n/2\rceil}}\)

根据题意我们有 \(F(x)G(x) \equiv 1 \pmod {x^{\lceil n / 2\rceil}}\),所以我们可以推出: \[ \begin{aligned} F(x)(G(x) - H(x)) &\equiv 0 \pmod {x^{\lceil n/2 \rceil}} \\ G(x) - H(x) &\equiv 0 \pmod {x^{\lceil n/2 \rceil}} \\ (G(x) - H(x))^2 &\equiv 0 \pmod {x^n} \\ G(x)^2 - 2G(x)H(x) + H(x)^2 &\equiv 0 \pmod {x^n} \\ F(x)\left(G(x)^2 - 2G(x)H(x) + H(x)^2\right) &\equiv 0 \pmod {x^n} \\ G(x) - 2H(x) + F(x)H(x)^2 &\equiv 0 \pmod {x^n} \\ G(x) &\equiv 2H(x) - F(x)H(x)^2 \pmod {x^n} \\ G(x) &\equiv H(x)\left(2 - F(x)H(x)\right) \pmod {x^n} \\ \end{aligned} \] 显然当 \(n = 1\) 时,\(G(x)\) 就是 \(F(x)\) 的唯一一项的逆元。

复杂度 \(T(n) = T\left( \frac12 \right) + O(n \log n) = O(n \log n)\)

多项式求导、积分

这个就是用来水的。

如果 \(\displaystyle F(x) = \sum_{i=0}^{n-1} a_ix^i\),那么 \(\displaystyle F'(x) = \sum_{i=1}^{n-1} i \cdot a_i x^{i-1}\)

并且还有 \(\displaystyle \int F(x) = \sum_{i=1}^{n-1} \frac {a_{i-1}x^i}i\)

多项式 ln

首先我们令原多项式为 \(F(x)\)\(\ln F(x) \equiv G(x) \pmod{x^n}\)。那么有: \[ \begin{aligned} \ln F(x) &\equiv G(x) \pmod{x^n} \\ \int (\ln F(x))' &\equiv G(x) \pmod{x^n} \\ \int \frac {F(x)}{F'(x)} &\equiv G(x) \pmod{x^n} \\ \end{aligned} \] 然后直接求就好了。

多项式 exp

首先我们令原多项式为 \(F(x)\)\(\exp(F(x)) \equiv G(x) \pmod{x^n}\)。那么有: \[ \begin{aligned} \exp(F(x)) &\equiv G(x) \pmod{x^n} \\ \ln G(x) - F(x) &\equiv 0 \pmod{x^n} \\\\ \text{令} f(x) = \ln G(&x) - F(x) \text{,则有} \\\\ f(x) &= f_0(x) - \frac{\ln f_0(x) - F(x)}{\frac1{f_0(x)}} \\ &= f_0(x)(1 - \ln f_0(x) + F(x)) \end{aligned} \] 所以我们直接按照牛顿迭代做就好了。

多项式开方

\[ \begin{aligned} \sqrt{F(x)} &\equiv F(x)^\frac12 \\ &\equiv \exp\left(\frac12 \ln F(x)\right) \pmod{x^n} \end{aligned} \]

按照上面的式子直接代就好了。

多项式快速幂

\[ F(x)^k \equiv \exp\left(k \ln F(x)\right) \pmod{x^n} \]

按照上面的式子直接代就好了。

UPD:这个有锅,待修

多项式三角函数

因为 \(\tan x = \frac{\sin x}{\cos x}\),所以我们只需要求出 \(\sin F(x)\)\(\cos F(x)\) 就好了。

首先对于一个复数 \(z = a + b\mathrm{i}\),它的模 \(|z| = \sqrt{a^2 + b^2}\)

那么 $|z|^2 = a^2 + b^2, z^2 = a^2 - b^2+ 2abi $,所以 \(z^2 + |z|^2 = 2a^2+2ab\mathrm i = 2a(a + b\mathrm i) = 2az\)

然后我们惊讶地发现,当 \(z \ne 0\) 时,\(\operatorname{Re}(z) = \frac{z^2 + |z|^2}{2z}\)

同理可得 \(z^2 - |z|^2 = 2b^2 - 2ab\mathrm i = 2b(b - a\mathrm i) = 2b\mathrm i(a + b\mathrm i) = 2bz\mathrm i\)

那么当 \(z \ne 0\) 时,也有 \(\operatorname{Im}(z) = \frac{z^2 - |z|^2}{2z\mathrm i}\)

所以根据 \(\mathrm{e}^{\mathrm{i}\theta}=\cos\theta+\mathrm{i}\sin\theta\),则有 \(\cos x = \operatorname{Re}(\mathrm e^{\mathrm ix}) = \frac{\mathrm e^{2\mathrm ix} + |\mathrm e^{2\mathrm ix}|}{2\mathrm e^{\mathrm ix}} = \frac{\exp(\mathrm ix)+\exp(-\mathrm ix)}2, \sin x = \operatorname{Im}(\mathrm e^{\mathrm ix}) = \frac{\exp(\mathrm ix)-\exp(-\mathrm ix)}{2\mathrm i}\)

其实推了那么多,直接把 \(\theta = -x\) 代进去就好了……

现在的问题只有,\(\mathrm i\) 在模意义下是什么?

因为 \(\mathrm i^2 = -1 = \mathrm e^{\mathrm i\pi}\),所以 \(\mathrm i\equiv\omega_n^{n/2} \equiv g^{\frac{P-1}{4}} \pmod P\)。所以 \(\mathrm i \equiv 3^{249561088} \equiv 911660635 \pmod {998244353}\)

然后代进去算就好啦!

多项式反三角函数

随便打开一张常见导数公式表,都应该可以看到: \[ \arcsin' x = \frac1{\sqrt{1-x^2}}, \arctan' x = \frac1{1+x^2} \] 所以 \[ \arcsin F(x) = \int\frac{F'(x)}{\sqrt{1-F(x)^2}}\mathrm{d}x\\ \arctan F(x) = \int\frac{F'(x)}{1+F(x)^2}\mathrm{d}x \] 随便套个板子就好了。

代码

目前包含上面所示的所有功能(有坑,勿用):