多项式操作汇总

2018/02/25 12:28
阅读数 66

#多项式操作汇总

最近学了不少多项式的小 trick,感觉不记一下容易忘。那我就把做法都摆在这里吧,代码还是自己去写了。(鉴于所有操作都是建立在 FFT 之上的,所以会写 FFT 的话所有东西的代码都能写出来了)

##多项式乘法

这个就是一切的基础,先把这个代码搞熟后面就都能写啦。

##多项式逆元

定义多项式 $g(x)$ 的逆元 $g^{-1}(x)$(以下为了方便简记为 $f(x)$)是满足如下等式的多项式:

$$ \begin{matrix} g(x) \cdot f(x) \equiv 1 & (\mod x^n) \end{matrix} $$

可以想象,模 $x^n$ 的意思就是把 $x^{n+1}$ 及更高的项都删掉,剩下的部分。为什么我们可以这样做呢?因为在解决实际问题的时候我们都只关心前 $n$ 项(即 $x^0 \sim x^{n-1}$ 的系数)。

求 $f(x)$ 的方法可能不止一种,但是我觉得用泰勒展开这个方法虽然麻烦但是好记(因为大多数问题可以用它——它是“通解”)。

注意:以下多项式都会在第一次用 $f(x)$ 表示过后就可能省掉后面的 $(x)$,你需要知道它是一个多项式。

我们先构造一个函数 $H(f) = f^{-1} - g$。你没有看错,这个 $H(f)$ 函数的自变量就是一个多项式。为什么要这样构造函数呢?因为可以发现当自变量 $f = g^{-1}$,即 $f$ 就是答案的时候,$H(f) = 0$。

我们用倍增的方法求这个 $f$,假设已经求出 $f_0(x)$ 是 $f$ 前 $\lceil \frac{n}{2} \rceil$ 项,即

$$ \begin{matrix} f_0 \equiv f & (\mod x^{\lceil \frac{n}{2} \rceil}) \end{matrix} $$

现在我们要用 $f_0$ 和 $g$ 表示出 $f$。利用我们刚才构造的函数,根据 $f_0$ 的定义有

$$ \begin{matrix} H(f_0) \equiv 0 & (\mod x^{\lceil \frac{n}{2} \rceil}) \end{matrix} $$

为了实现上面黑体字的目的,我们对 $H(f)$ 在 $f_0$ 处进行泰勒展开(想点进去看的请翻到文章末尾),即用下面这个式子去逼近 $H(f)$

$$ H(f) = \sum_ {i = 0}^{+ \infty} { \frac{H^{[i]}(f_0) (f-f_0)^i}{i!} } $$

注意上面这个等式不是模意义下的,不需要取模它们就相等。

接下来我们观察一下 $(f-f_0)^i$,由于 $f - f_0 \equiv 0 (\mod x^{\lceil \frac{n}{2} \rceil})$,发现当 $i = 2$ 时,最高次项平方之后次数一定 $\ge n$,所以有 $\forall i > 1, (f-f_0)^i \equiv 0 (\mod x^n)$,那么上面的泰勒展开的无穷多项就只剩了两项,整理出来就是

$$ \begin{matrix} H(f) \equiv H(f_0) + H'(f_0)(f - f_0) & (\mod x^n) \\ \because H(f) \equiv 0 & (\mod x^n) \\ \therefore H(f_0) + H'(f_0)(f - f_0) \equiv 0 & (\mod x^n) \end{matrix} $$

移项得到

$$ \begin{matrix} f \equiv f_0 - \frac{H(f_0)}{H'(f_0)} & (\mod x^n) \end{matrix} $$

至此我们得到了牛顿迭代的公式,以后可以记它,就不用每次都泰勒展开了。接下来的工作就是把刚才构造的 $H(f)$ 带进去。

$$ \begin{matrix} f \equiv 2f_0 - gf_0 & (\mod x^n) \end{matrix} $$

递归下去,再用这个式子回溯,就求出来啦!

时间复杂度:$T(n) = T(\frac{n}{2}) + O(n\log n) = O(n\log n)$,发现这个小秘密后,我们可以无限套,理论复杂度不变233

##多项式除法 & 取模

注意这里的除法不是在模意义下的!所以它会有商和余数,即如果我要求 $\frac{A(x)}{B(x)}$,我就是要求两个多项式 $D(x)$ 和 $R(x)$,使得它们满足下面这样一个等式

$$ A(x) = B(x)D(x) + R(x) $$

现在我们记 $n$ 为 $A$ 的次数,$m$ 为 $B$ 的次数,那么有 $D$ 的次数为 $\mathrm{max}(n - m, 0)$,$R$ 的次数 $\le m - 1$。

记 $F(x)$ 的次数为 $t$, $F^R(x) = F(\frac{1}{x}) \cdot x^t$,直观理解就是把 $F$ 的系数反转一下。

接下来将 $\frac{1}{x}$ 带入到原式中,再两边同乘 $x^n$,看看会发生什么

$$ x^nA(\frac{1}{x}) = x^{m}B(\frac{1}{x}) \cdot x^{n-m}D(\frac{1}{x}) + x^{n-m+1} \cdot x^{m-1}R(\frac{1}{x}) \\ \therefore A^R(x) = B^R(x)D^R(x) + x^{n-m+1}R^R(x) $$

如果我们将新的等式放在模 $x^{n-m+1}$ 的意义下,$R(x)$ 就被消掉了!与此同时 $D^R(x)$ 最高次为 $x^{n-m}$,故不会受到任何影响,即模意义下求出的 $D^R(x)$ 与非模意义下的完全相同。

$$ \begin{matrix} A^R(x) \equiv B^R(x)D^R(x) & (\mod x^{n-m+1}) \\ \therefore D^R(x) \equiv A^R(x)[B^R(x)]^{-1} & (\mod x^{n-m+1}) \end{matrix} $$

$D(x)$ 就是 $D^R(x)$ 反转一下系数,把 $D(x)$ 代到最初的式子里就能得到 $R(x)$ 了。

###多项式多点求值

任务:给出多项式 $F(x)$ 和集合 ${ x_1, x_2, \cdots , x_n }$,要求返回一个集合 ${ F(x_1), F(x_2), \cdots , F(x_n) }$。

构造多项式 $A(x) = (x - x_1)(x - x_2)\cdots(x - x_n)$,令 $G(x) \equiv F(x) (\mod A(x))$,那么对于 $\forall i \in [1, n], G(x_i) = F(x_i)$。

为什么呢?因为

$$ F(x) = A(x)D(x) + G(x) $$

而 $\forall i \in [1, n], A(x_i) = 0, \therefore F(x_i) = G(x_i)$。

于是就可以分治了。令 $A_l(x) = \prod_{i = 1}^{\lfloor \frac{n}{2} \rfloor} { (x - x_i) }, A_r(x) = \prod_{i = \lfloor \frac{n}{2} \rfloor + 1}^n { (x - x_i) }$,然后把 $F(x)\ \mod A_l(x)$ 和 $F(x)\ \mod A_r(x)$ 扔下去递归了。

时间复杂度:$O(n \log^2 n)$

##多项式 ln & exp

应该有不少人好奇这两个操作的组合意义是什么。事实上这个问题我并不是很清楚,我们也许可以通过泰勒展开后的系数研究一下它的组合意义,但它们的价值主要不在于组合意义,而在于其他方面的应用。

具体应用在讲完做法后立刻就会有一个,所以不必着急,我们先看看多项式取 ln 怎么求。

###多项式取 ln

注意到这样一个等式

$$ (\ln f(x))' = \frac{f'(x)}{f(x)} $$

于是积分一下就可以轻易地求出 $\ln f(x)$ 了

$$ \ln f(x) = \int \frac{f'(x)}{f(x)} $$

其中,求导和积分都能在 $O(n)$ 时间内求出,所以总时间复杂度 $O(n)$。

细心的读者一定会问:积分之后,常数项如何确定?注意到这里的 $[x^0]f(x)$ 必须为 $1$,也就是说 $[x^0] \ln f(x)$ 一定是 $0$,那么积分完后常数项为 $0$ 就好了。(如果 $[x^0]f(x) \ne 1$ 怎么求?QAQ 我也不会,因为我们似乎很难找到 $\ln c (c > 0)$ 在剩余系下的表示……)

###多项式求 exp

我们要求这样的一个函数 $f(x)$,满足

\begin{matrix} f(x) \equiv e^{g(x)} & (\mod x^n) \end{matrix}

两边取对数,我们有

\begin{matrix} \ln f(x) \equiv g(x) & (\mod x^n) \end{matrix}

我们还是考虑倍增求 $f$,套用上面泰勒展开推出来的结果,构造函数 $H(f) = \ln f - g$,令 $f_0 \equiv f (\mod x^{\lceil \frac{n}{2} \rceil})$,于是得到

\begin{matrix} f \equiv f_0 - \frac{\ln f_0 - g}{f_0^{-1}} & (\mod x^n) \\ f \equiv f_0(1 - \ln f_0 + g) & (\mod x^n) \end{matrix}

这样就 $O(n \log n)$ 解决啦,你会发现求 exp 其实依赖于求 ln。同样地我们只能求 $[x^0]g(x) = 0$ 的 $e^{g(x)}$。

接下来就是一个经典的应用。

###多项式乘方

求 $f(x)$ 满足

\begin{matrix} f(x) \equiv g(x) ^ k & (\mod x^n) \end{matrix}

指数相关,考虑两边取对数

\begin{matrix} \ln f(x) \equiv k \ln g(x) & (\mod x^n) \\ f(x) = e^{k \ln g(x)} & (\mod x^n) \end{matrix}

这就解决了?别忘了常数项的问题,问题有两个:

  • $[x^0]g(x) > 1$,我们可以将常数项提出来,得到 $g'(x)$(注意不是导数,这个就是 $g(x)$ 的每项乘上常数项的逆元),那么问题变成了求 $(g'(x))^k c^k$,$c$ 代表常数项,就是在上面的过程进行完后每项乘上 $c^k$ 即可;
  • $[x^0]g(x) = 0$,先位移到常数项不为 $0$,即得到 $g'(x) = \frac{g(x)}{x^d}$,$d$ 表示前缀连续 $0$ 的个数,那么问题变成了求 $(g'(x))^k x^{kd}$,就是上面的过程进行完后再位移 $kd$ 位即可。

至此多项式乘方就完整地解决了。

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部