多项式学习笔记

2021-12-02

记录了多项式基础内容的一些理解和推导过程。
鸣谢：
BILL666 的多项式全家桶博客
OI-Wiki 多项式部分

0. 前置知识

多项式的系数表示和点值表示

令 $F(i)$ 表示一个 $n$ 次多项式，$F(i)=\sum\limits_{i=0}^{n}a_ix^i$ 为 $F(i)$ 的系数表示。
将不同的 $x_0,x_1,\dots,x_n$ 带入 $F(i)$，会对应得到 $y_0,y_1,\dots,y_n$，即在平面直角坐标系上取两两不同的 $n+1$ 个点 $(x_i,y_i),i\in[0,n]$，这 $n+1$ 个点便可以唯一确定 $F(x)$。我们称 $\{(x_0,y_0),(x_1,y_1),\dots,(x_n,y_n)\}$ 为 $F(x)$ 的点值表示。

复数

见高中数学必修 $2$。

单位根

在复平面上，以 $1$ 为半径作圆，所得到的圆叫做单位圆。
将单位圆 $n$ 等分，将单位圆的 $n$ 等分点所代表的复数称为 $n$ 次单位根。
令 $\omega_n$ 表示 $n$ 次单位根，有 $\omega_n^0=\omega_n^n=1$，$\omega_{n}^{k}=\cos k\frac{2\pi}{n}+i\sin k\frac{2\pi}{n}$。

单位根有如下性质：

1. 所有的 $\omega_n^i,i\in[0,n)$ 不同。
2. $\omega_{2n}^{2k}=\omega_n^k$。
3. $\omega_n^{k+\frac{n}{2}}=-\omega_n^k$。

单位根反演定理：
$[n\mid k]=\dfrac{1}{n}\sum\limits_{i=0}^{n-1}(\omega_n^k)^i$。

原根

定义：设 $p$ 是正整数，$a$ 是整数，若 $a$ 模 $p$ 的阶等于 $\varphi(p)$，则称 $a$ 为模 $p$ 的一个原根，记 $a$ 的最小原根为 $g$。
$998244353=7\times 17\times 2^{23}+1,g(998244353)=3$。
原根满足上述单位根的性质，即 $(g^{\frac{p-1}{n}})^k\equiv \omega_n^k\pmod{p}$。注意此处必须满足 $n\mid p-1$。

1. FFT

令两个多项式 $A(x),B(x)$ 相乘，结果为 $F(x)$。
FFT 的基本思路是将 $A(x),B(x)$ 求值转化为点值表示，在点值表示下直接相乘得到 $F(x)$ 的点值表示，最后将 $F(x)$ 插值转化回系数表示。
点值相乘的复杂度为 $\Theta(n)$，现在需要 $\Theta(n\log n)$ 进行求值和插值的过程。
以下的 $n$ 均为 $2$ 的整次幂，当次数不足时将高位补全即可。
设 $f(x)=a_0+a_2x+\dots+a_{n-2}x^{\frac{n-2}{2}},g(x)=a_1+a_3x+\dots+a_{n-1}x^{\frac{n-1}{2}}$。
将 $A(x)$ 按奇偶性分类，即

$$\begin{aligned} A(x)&=a_0+a_1x+\dots+a_{n-1}x^{n-1}\\ &=(a_0+a_2x^2+\dots+a_{n-2}x^{n-2})\\ &=f(x^2)+x\cdot g(x^2) \end{aligned}$$

带入单位根，根据单位根的性质可以推导出
$A(\omega_n^k)=f(\omega_{\frac{n}{2}}^k)+\omega_n^k\cdot g(\omega_{\frac{n}{2}}^k),A(\omega_n^{k+\frac{n}{2}})=f(\omega_{\frac{n}{2}}^k)-\omega_n^k\cdot g(\omega_{\frac{n}{2}}^k)$。
这样我们计算 $A(\omega_n^k)$ 时可以同时得到 $A(\omega_n^{k+\frac{n}{2}})$ 的值，求值的复杂度成功优化到了 $\Theta(n\log n)$。

考虑插值。我们现在已经求出了 $F(x)$ 在 $\omega_n^0,\omega_n^1,\dots,\omega_n^{n-1}$ 处的点值，希望求出 $F(x)$ 各项的系数 $b_i$。
我们构造 $h(x)=\sum\limits_{i=0}^{n-1}F(\omega_n^i)x^i=\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}b_j(\omega_n^i)^jx^i$。
将 $x=\omega_n^0,\omega_n^{-1},\dots,\omega_n^{-(n-1)}$ 带入 $h(x)$，有

$$\begin{aligned} h(\omega_n^{-k})&=\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}b_j(\omega_n^i)^j(\omega_n^{-k})^i\\ &=\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}b_j(\omega_n^{j-k})^i\\ &=\sum\limits_{j=0}^{n-1}b_j\sum\limits_{i=0}^{n-1}(\omega_n^{j-k})^i \end{aligned}$$

由单位根反演，可以得到 $h(\omega_n^{-k})=\sum\limits_{j=0}^{n-1}b_jn[n\mid j-k]=nb_k$。
所以我们求出 $h(x)$ 在 $x=\omega_n^0,\omega_n^{-1},\dots,\omega_n^{-(n-1)}$ 处的点值，再除以 $n$ 即为答案。

这样我们就在 $\Theta(n\log n)$ 的时间内完成了多项式乘法。

但如果直接模拟上述过程，需要递归实现，常数过大。考虑优化，可以把每个数直接交换到对应位置上，通过前后翻转下标的二进制位 $\Theta(n)$ 实现。这样就将递归变成了迭代，常数也减小了很多。

2. NTT

支持取模，可以进行模意义下的多项式乘法。
用原根代替单位根，减少了计算单位根和复数时不必要的常数。
注意在某些特定情况下取模可能造成冲突。

3. 多项式求逆

以下推导均在模 $998244353$ 下进行。
给定 $n-1$ 次多项式 $F(x)$，求多项式 $G(x)$ 满足 $F(x)\cdot G(x)\equiv 1\pmod{x^n}$。
此时称 $G(x)$ 是 $F(x)$ 的逆，记作 $F^{-1}(x)$。

考虑倍增求解，不妨设已经求得多项式 $G_0(x)$ 满足 $F(x)\cdot G_0(x)\equiv 1\pmod{x^{\lceil\frac{n}{2}\rceil}}$
$G(x)$ 也同时满足 $F(x)\cdot G(x)\equiv 1\pmod{x^{\lceil\frac{n}{2}\rceil}}$。
所以有

$$\begin{aligned} F\cdot(G-G_0) &\equiv 0&\pmod{x^{\lceil\frac{n}{2}\rceil}}\\ (G-G_0)^2 &\equiv 0&\pmod{x^{\lceil\frac{n}{2}\rceil}}\\ F\cdot (G^2+G_0^2-2G\cdot G_0)&\equiv 0&\pmod{x^{\lceil\frac{n}{2}\rceil}}\\ G-2G_0+F\cdot G_0^2&\equiv 0&\pmod{x^{\lceil\frac{n}{2}\rceil}}\\ G&\equiv 2G_0-F\cdot G_0^2&\pmod{x^{\lceil\frac{n}{2}\rceil}}\\ \end{aligned}$$

特别地，$F(x)=c$ 时，$G(x)=c^{p-2}$，其中 $p$ 是模数。

4. 多项式 ln

$f(x)$ 对数函数的定义：
$\ln(1-f(x))=-\sum\limits_{i=1}^{+\infty}\dfrac{f^i(x)}{i}$
保证 $f(0)=1$。

给定 $n-1$ 次多项式 $F(x)$，求多项式 $G(x)$ 满足 $G(x)\equiv \ln F(x)\pmod{x^n}$。
两边同时求导得到 $G’\equiv(\ln F)’\pmod{x^n}$，
即 $G’\equiv\dfrac{F’}{F}\pmod{x^n}$。
再积分一下，即 $G\equiv\int\dfrac{F’}{F}\pmod{x^n}$。

5. 多项式 exp

$f(x)$ 指数函数的定义：
$\exp f(x)=e^{f(x)}=\sum\limits_{i=1}^{+\infty}\dfrac{f^i(x)}{i!}$

需要用到多项式牛顿迭代，有如下递归式（$G_0(x)$ 的含义与多项式求逆一致）：
$G(x)\equiv G_0(x)-\dfrac{F(G_0(x))}{F’(G_0(x))}\pmod{x^n}$
特殊处理边界 $n=1$ 的情况。
推导过程暂时不会。

给定 $n-1$ 次多项式 $F(x)$，求多项式 $G(x)$ 满足 $G(x)\equiv \exp F(x)\pmod{x^n}$。保证 $F(0)=0$。

将原式化成 $\ln G(x)-F(x)\equiv 0\pmod{x^n}$ 的形式，带入牛顿迭代的表达式：

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

递归边界 $G(x)\equiv 1\pmod{x^n}$。

6. 多项式开根

给定 $n-1$ 次多项式 $F(x)$，求多项式 $G(x)$ 满足 $G^2(x)\equiv F(x)\pmod{x^n}$。
将 $G^2(x)-F(x)\equiv 0\pmod{x^n}$ 代入牛顿迭代的表达式可得：
$G(x)=G_0(x)-\dfrac{G_0^2(x)-F(x)}{2G_0(x)}\pmod{x^n}$
递归边界 $G(x)=\sqrt{f(0)} \pmod{p}$，求出 $a_0$ 的二次剩余即可。

7. 多项式快速幂

给定 $n-1$ 次多项式 $F(x)$，求多项式 $G(x)$ 满足 $G(x)\equiv F^k(x)\pmod{x^n}$。保证 $F(0)=1$。

可以由多项式定理证明 $F^k(x)\equiv F^{k\bmod p}(x)$。证明略。
于是容易得到 $G(x)\equiv e^{(k\bmod p)\ln F(x)}\pmod{x^n}$。

8. 多项式除法/取模

给定 $n-1$ 次多项式 $F(x),G(x)$，求 $Q(x),R(x)$ 满足 $F(x)=Q(x)G(x)+R(x)$。
定义一个多项式 $F(x)$ 的系数数组翻转后形成的新多项式为 $F_R(x)$，即形式化地，$F_R(x)=\sum\limits_{i=0}^{n-1}a_{n-i+1}x^i$。

推导过程如下：

$$\begin{aligned} F(\dfrac{1}{x})&=Q(\dfrac{1}{x})G(\dfrac{1}{x})+R(\dfrac{1}{x})\\ x^{n-1}F(\dfrac{1}{x})&=x^{n-m}Q(\dfrac{1}{x})\cdot x^{m-1}G(\dfrac{1}{x})+x^{n-m+1}\cdot x^{m-2}R(\dfrac{1}{x})\\ F_R(x)&=Q_R(x)G_R(x)+x^{n-m+1}R_R(x)\\ F_R(x)&\equiv Q_R(x)G_R(x)\pmod{x^{n-m+1}}\\ Q_R(x)&\equiv\dfrac{F_R(x)}{G_R(x)}\pmod{x^{n-m+1}} \end{aligned}$$

求出 $Q(x)$ 后有 $R(x)=F(x)-Q(x)G(x)$。

9. 常系数齐次线性递推

本质上是求 $x^n \bmod G(x)$ 的结果，其中 $G(x)=x^k-p_1x^{k-1}-p_2x^{x-2}-\cdots -p_kx^0$。多项式倍增快速幂的同时对 $G(x)$ 取模即可。

10. 例题（见做题记录 3）

部分题目包含了生成函数的内容。
P4389 付公主的背包
P3338 [ZJOI2014] 力
P4841 [集训队作业2013] 城市规划
CF528D Fuzzy Search
CF438E The Child and Binary Tree
P4173 残缺的字符串

11. 多项式模板（持续更新/卡常）

Code

Notes