RainAir
My OI Blog
RainAir
多项式初步

多项式算法学习笔记

定义

形如 $\sum a_ix^{i}$ 的式子被称为多项式。定义多项式中每个单项式叫做这个多项式的项,定义多项式的次数为项的最高次数。显然 $(n+1)$ 个点可以唯一确定一个次数为 $n$ 的多项式。
接下来我们首先来看一下多项式的基本运算怎么实现(要不然谁用啊)

多项式加减

直接对齐相同次数然后系数直接加减就可以了吧。。。时间复杂度 $O(n)$,难度:普及组 T1(虽然这个级别已经不存在了233)

多项式乘法

首先我们考虑一下我们平时如何手算多项式算法。显然我们都是 $O(n^2)$ 暴力算的,所以就有了一个枚举所有可能的二元组然后统计答案的暴力做法。
当然在常规题目中我们会使用一种叫做 FFT(快速傅里叶变换) 的 $O(nlogn)$ 的优秀算法来计算,详情请查看这篇文章
哈哈你一定学完 FFT 然后回来了!我们来考虑一下如果多项式乘法在模意义下怎么做。
有一种叫做 NTT (快速数论变换)的东西,它把每次我们做快速傅里叶变换时用到的 $\omega$ 重新定义了一下。大概是令 $g$ 为模数 $p$ 的原根,我们就可以取 $w_n = g^{\frac{p-1}{n}}$。然后 IDFT 的时候直接乘逆元就可以了。
至于这个原根怎么找。。。一般你碰到模数为 $998244353$ 的时候就想下可不可以 NTT,因为 $998244353$ 是一个常用的 NTT 模数,一个原根是 $3$。
中心代码大致如下:

好了接下来才是关于多项式的一些基本的稍微硬核一点的操作。

确定多项式

上面提到了 $(n+1)$ 个点可以唯一确定一个次数为 $n$ 的多项式。
现在给定 $n$ 个点,请你确定这个多项式并且将 $k$ 代入求值。

做法一:高斯消元

我们暴力建方程然后暴力高斯消元!$O(n^3)$。
什么你连高斯消元都不会?题目链接
其实就是暴力解方程啦~奉上高斯消元模板题的代码:

做法二:拉格朗日插值

背下式子:
设该多项式为 $f(x)$,第 $i$ 个点的坐标为 $(x_i,y_I)$,需要求在 $k$ 点的取值。
$$f(k) = \sum_{i=0}^n y_i \prod_{i \neq j}\frac{k-x_j}{x_i-x_j}$$
证明显然:因为这个式子满足了如果代入 $x_i$ 就肯定会返回 $y_i$。根据 $n+1$ 个点唯一确定一个多项式,就可以知道这个多项式等价于原多项式了。

扩展阅读:维基百科-拉格朗日插值
(中文维基,需要科学上网)

多项式求逆

题目链接
给定一个多项式 $F(x)$,让你求出一个多项式 $G(x)$,满足 $F(x) * G(x) \equiv 1(\mod x^n)$
我们可以考虑倍增地构造多项式 $G$。首先我们把这个式子进行一些化简。
\begin{align}
F(x)G(x)-1 &\equiv 0(\mod x^n) \\
F^2(x)G^2(x)+1-2F(x)G(x) &\equiv 0(\mod x^{2n}) \\
2F(x)G(x)-F^2(x)G^2(x) &\equiv 1(\mod x^{2n}) \\
2F(x)G(x)-F^2(x)G^2(x) &\equiv 1(\mod x^{2n}) \\
F(x)(2G(x)-F(x)G^2(x)) &\equiv 1(\mod x^{2n}) \\
\end{align}
不难发现最后一个式子的范围扩大到原来的 $2$ 倍,并且又凑成了一开始的形式。
我们考虑迭代处理,首先当规模为 $1$ 时显然答案系数就是对应系数的逆元。
我们设对于规模为 $n$ 的问题得到的多项式为 $G_0$,我们想要推出扩大一倍规模的答案 $G_1$,根据上面的推导,可以有
$$G_1 = 2G(x)-F(x)G^2(x) = G(x)(2-F(x)G(x))$$
所以我们直接两遍 NTT 就能扩大一倍的问题规模了。
时间复杂度:$T(n) = 2T(n/2) + n log n \Rightarrow O(nlogn)$。
这里就只给迭代写法啦 qwq 貌似迭代确实比递归快很多呢。

多项式除法

题目链接
给定一个 $n$ 次多项式 $F(x)$ 和一个 $m$ 次多项式 $G(x)$,求出两个多项式 $Q(x),R(x)$,满足:
* $Q(x)$ 次数为 $n-m$,$R(x)$ 次数小于 $m$。
* $F(x) = Q(x)G(x)+R(x)$。
显然如果能整除的话我们直接求个逆就可以了。那现在有余数怎么办啊 Orz…….
别急,我们首先定义一种操作 R(reverse),满足:$A_R(x) = x^nA(\frac{1}{x})$。
不难看出 $R$ 操作的本质是多项式翻转。所以我们就可以 $O(n)$ 完成这个操作。
现在我们尝试对我们要构造的东西做一些改变。
\begin{align}
F(x) &= Q(x)G(x)+R(x) \\
F(\frac{1}{x}) &= Q(\frac{1}{x})G(\frac{1}{x})+R(\frac{1}{x}) \\
x^nF(\frac{1}{x}) &= x^{n-m}Q(\frac{1}{x})x^mG(\frac{1}{x})+x^{n-m+1}x^{m-1}R(\frac{1}{x}) \\
F_R(\frac{1}{x}) &= Q_R(\frac{1}{x})G_R(\frac{1}{x})+x^{n-m+1}R_R(\frac{1}{x}) \\
\end{align}
我们考虑两边对 $x^{n-m+1}$ 取模。
\begin{align}
F_R(\frac{1}{x}) &\equiv Q_R(\frac{1}{x})G_R(\frac{1}{x}) (\mod x^{n-m+1}) \\
Q_R(\frac{1}{x}) &\equiv F_R(\frac{1}{x})G_R^{-1}(\frac{1}{x}) \\
\end{align}
我们求一遍 $G_R$ 的逆,然后用 NTT 乘起来,就可以得到 $Q_R$ 了,最后
$$R(x) = F(x)-G(x)Q(x)$$
直接计算出来余数就可以了。
时间复杂度瓶颈在于多项式求逆,所以是 $O(nlogn)$。
代码就不贴了。就是上面的一些简单运用。

多项式求导/积分

都是非常简单的东西了。
$$f(x) = \sum_{i=0}^n a_ix^i$$
根据求导的加法法则和幂函数可以轻松得到:
\begin{align}
f'(x) &= \sum_{i=1}^n i\times a_ix^{i-1} \\
\int_l^r f(x)d(x) &= \sum_{i=1}^{n+1} \frac{a_{i-1}r^i}{i} – \sum_{i=1}^{n+1} \frac{a_{i-1}l^i}{i}
\end{align}
补充一些同样适用于多项式的求导基本法则:
$(cA(x))’ = cA'(x)$
$(A(x)+B(x))’ = A'(x)+B'(x)$
$(A(x)B(x))’ = A'(x)B(x)+A(x)B'(x)$
$(\frac{A(x)}{B(x)})’ = \frac{A'(x)B(x)-A(x)B'(x)}{B^2(x)}$
写这些主要是为了介绍后面的牛顿迭代 $qwq$

多项式牛顿迭代

处理多项式复合的高级神器 Orz
问题大概是这样的:给出 $G(x)$,求 $F(x)$ 满足 $G(F(x)) \equiv 0 (\mod x^n)$。
首先为了让像我这样萌萌哒的弱校初中选手也能看懂,我决定放一些前置芝士。

前置芝士1:Taylor 展开

这个大家都会 qwq。

Taylor 展开(泰勒展开)是一种用函数在某点的信息描述其附近取值的公式,也就是拟合某点及其周围的取值啦qwq。
具体来说我们从头开始构造这个拟合函数,设我们要使 $P$ 及其周围一段区间拟合这个原函数。首先我们可以使得我们构造出的函数和待拟合的函数在 $P$ 的取值相等。但是发现这只有一个值?一点也不像怎么办?我们可以使得他们的二阶倒数,三阶导数…..一直相等下去,然后我们就会发现这两个函数在那附近神奇的重合了!我们看个 GIF 来详细的了解这个过程。
https://blog.aor.sd.cn/wp-content/uploads/2019/02/v2-9dd69ab2c20ca721bc0979d7ebaa0253_b.gif
所以我们就可以得到 Taylor 展开来拟合多项式的式子了:
$$f(x) \approx g(x) = g(0) + \sum_{i=1} \frac{f^{(i)}(0)}{i!}x^i$$
其中 $f^{(n)}(x)$ 表示对原函数图像 $x$ 这个点进行 $n$ 阶求导。
如果描述听不懂的话建议大家去看一下上面的视频的…毕竟视频里有图还有可爱的 $\pi$~

回到多项式牛顿迭代上

我们考虑使用和多项式求逆一样的 trick:倍增来构造答案多项式。
首先当 $n=1$ 时,$G(F(x)) \equiv 0 (\mod x)$,这个就是要单独求出来的。
现在我们假设已经求出了
$$G(F_0(x)) \equiv 0(\mod x^n)$$
考虑如何扩展到 $x^{2n}$ 下,我们把 $G(F(x))$ 放到 $F_0(x)$ 上做 Taylor 展开
$$G(F(x)) = G(F_0(x)) + \sum_{i=1} \frac{G^{(i)}}{i!}(F(x)-F_0(x))^i$$
因为倍增构造,我们可以发现 $F(x)$ 和 $F_0(x)$ 后 $n$ 项相同,所以 $(F(x)-F_0(x))^2$ 的最低非 $0$ 项次数大于 $2n$。所以可以得到
$$G(F(x)) \equiv G(F_0(x))+G'(F_0(x))(F(x)-F_0(x)) (\mod x^{2n})$$
然后因为我们要求的 $G(F(x))$ 需要满足 $G(F(x)) \equiv 0(mod x^{2n})$,所以可以推一波式子:
\begin{align}
G(F_0(x))+G'(F_0(x))F(x)-G'(F_0(x))F_0(x) &\equiv 0(\mod x^{2n}) \\
F(x) &\equiv F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}
\end{align}
按照多项式求逆那样的套路迭代计算就可以了,我们来看一下一些经典的题目。

多项式开方

题目链接
给定一个多项式 $A(x)$,要求求出一个多项式 $B(x)$,满足 $B^2(x) \equiv A(x)(\mod x^n)$
简单的变换:$B^2(x)-A(x) \equiv 0(\mod x^n)$。
设 $G(B(x)) = B^2(x)-A(x)$,则 $G'(B(x)) = 2B(x)$,使用牛顿迭代法:
\begin{align}
B(x) & \equiv B_0(x)-\frac{B_0^2(x)-A(x)}{2B_0(x)} \\
& \equiv \frac{F_0^2(x)+A(x)}{2F_0(x)}
\end{align}
然后就可以直接迭代计算了。时间复杂度 $O(nlogn)$。

多项式求 ln

题目链接
给定一个多项式 $A(n)$,求一个多项式 $B(n)$,满足 $B(n) = ln A(n)$。
我们设 $G(x) = F(A(x))$,定义 $F(x) = ln(x)$。
那么显然 $G'(x) = F'(A(x))A'(x) = \frac{A'(x)}{A(x)}$。
那么求逆就可以算出 $G’$。然后因为求导和不定积分互逆,所以对 $G’$ 求一个不定积分就可以了。
代码不贴了(主要是后面有大杂烩)

多项式求 exp

题目链接
多项式大杂烩,练习之前学的怎么样了qwq
给定一个多项式 $A(x)$,要你求出一个 $B(x)$,满足 $B(x) \equiv e^{A(x)} (\mod x^n)$。
我们考虑计算出
$$B(x) \equiv e^{A(x)} (\mod x^n)$$
变形一下可得
$$lnB(x)-A(x) \equiv 0 (\mod x^n)$$
设 $G(B(x)) = lnB(x)-A(x)$,然后直接套用牛顿迭代方法:
首先求导:得到 $G'(B(x)) = \frac{1}{B(x)}$
然后代入牛顿迭代公式,得到
\begin{align}
B(x) & \equiv B_0(x) – \frac{G(B_0(x))}{G'(B_0(x))} \\
B(x) & \equiv B_0(x) – B_0(x)(lnB_0(x)-A(x)) \\
B(x) & \equiv B_0(x)(1-lnB_0(x)+A(x))
\end{align}
因为 $A(0)=0$,所以 $B(x)$ 的常数项是 $1$。(有些牛顿迭代题目要用二次剩余算系数但是我还没接触过QAQ)
然后就是板子大全了qwq
放一下代码吧:

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/513
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

多项式初步
多项式算法学习笔记 定义 形如 $\sum a_ix^{i}$ 的式子被称为多项式。定义多项式中每个单项式叫做这个多项式的项,定义多项式的次数为项的最高次数。显然 $(n+1)$ 个点可以唯一确定一个…
扫描二维码继续阅读
2019-02-28
标签
近期评论