多项式#

$$最基础的数学对象.$$
  • 数系（自然数、整数、有理数、实数、复数）
  • 代数结构（群、环、域、向量空间）

多项式是连接它们的第一个纽带.

插值#

给定 $n$ 个 $x$ 坐标不同的点，恰好可以用唯一的 $n-1$ 次多项式穿过.

相应地，一个 $n-1$ 次多项式，可以由 $n$ 个 $x$ 坐标不同的点确定.

范德蒙德行列式#

形如以下形式的行列式，称为范德蒙德行列式：

$$D_n= \begin{vmatrix} 1&x_0&x_0^2&\cdots&x_0^{n-1}\\ 1&x_1&x_1^2&\cdots&x_1^{n-1}\\ \vdots&\vdots&\vdots&&\vdots\\ 1&x_{n-1}&x_{n-1}^2&\cdots&x_{n-1}^{n-1} \end{vmatrix} =\prod_{0\leq i<j<n}(x_j-x_i)$$

证明如下：

将 $D_n$ 看作关于 $x_{n-1}$ 的多项式，其次数不超过 $n-1$ .

当 $x_{n-1}=x_i$ ，其中 $0\leq i<n-1$ 时，行列式中存在两行相同，故 $D_n=0$ .

因此，

$$D_n=C\prod_{i=0}^{n-2}(x_{n-1}-x_i)$$

按最后一行展开，$x_{n-1}^{n-1}$ 的系数为 $D_{n-1}$ ，即 $C=D_{n-1}$ .

又，$D_1=1$ ，递推得到：

$$D_n=\prod_{0\leq i<j<n}(x_j-x_i)$$

特别地，当所有 $x_i$ 两两不同时，$D_n\neq0$ .

设，

$$f(x)=\sum_{j=0}^{n-1}a_jx^j$$

给定 $n$ 个横坐标两两不同的点 $(x_i,y_i)$ ，求 $f(x_i)=y_i$ 等价于求解：

$$\begin{pmatrix} 1&x_0&\cdots&x_0^{n-1}\\ 1&x_1&\cdots&x_1^{n-1}\\ \vdots&\vdots&&\vdots\\ 1&x_{n-1}&\cdots&x_{n-1}^{n-1} \end{pmatrix} \begin{pmatrix}a_0\\a_1\\\vdots\\a_{n-1}\end{pmatrix} =\begin{pmatrix}y_0\\y_1\\\vdots\\y_{n-1}\end{pmatrix}$$

系数矩阵的行列式非零，故方程组有唯一解.

即，$n$ 个横坐标两两不同的点，唯一确定一个次数不超过 $n-1$ 的多项式.

这里的运算在域上进行，如实数域、复数域或模质数 $p$ 的有限域. 在有限域中，“不同”指模 $p$ 意义下不同.

拉格朗日插值#

已知 $n$ 个点 $(x_i,y_i)$ ，其中 $x_i$ 两两不同，求次数不超过 $n-1$ 的多项式 $f(x)$ .

考虑构造 $n$ 个多项式，使第 $i$ 个多项式仅在 $x_i$ 处取值为 $1$ ，在其他给定横坐标处取值为 $0$ .

设，

$$L_i(x)=\prod_{\substack{0\leq j<n\\j\neq i}}\frac{x-x_j}{x_i-x_j}$$

则，

$$L_i(x_j)=[i=j]$$

故，

$$f(x)=\sum_{i=0}^{n-1}y_iL_i(x) =\sum_{i=0}^{n-1}y_i\prod_{\substack{0\leq j<n\\j\neq i}}\frac{x-x_j}{x_i-x_j}$$

每一项的次数不超过 $n-1$ ，且在 $x_i$ 处仅剩下第 $i$ 项，其值为 $y_i$ . 根据插值唯一性，这就是所求多项式.

直接代入求某个 $f(k)$ ，需要 $O(n^2)$ 次域运算. 这里求的是一个点的值，不必展开多项式的所有系数.

连续点值插值#

特别地，当 $x_i=i$ ，即已知 $f(0),f(1),\dots,f(n-1)$ 时，

$$\begin{aligned} \prod_{\substack{0\leq j<n\\j\neq i}}(i-j) &=\left(\prod_{j=0}^{i-1}(i-j)\right)\left(\prod_{j=i+1}^{n-1}(i-j)\right)\\ &=i!\cdot(-1)^{n-1-i}(n-1-i)! \end{aligned}$$

分子可以利用前缀积和后缀积求出.

设，

$$P_i=\prod_{j=0}^{i-1}(k-j),\qquad S_i=\prod_{j=i}^{n-1}(k-j)$$

其中 $P_0=S_n=1$ ，则，

$$P_{i+1}=P_i(k-i),\qquad S_i=(k-i)S_{i+1}$$

故，

$$f(k)=\sum_{i=0}^{n-1}\frac{(-1)^{n-1-i}y_iP_iS_{i+1}}{i!(n-1-i)!}$$

预处理阶乘及其逆元后，每次求值的时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ .

在模质数 $p$ 意义下：

  • 要求 $n\leq p$ ，保证给定横坐标互不相同，且分母非零.
  • 除法转化为乘逆元，$a^{-1}\equiv a^{p-2}\pmod p$ ，其中 $a\not\equiv0\pmod p$ .
  • 若 $k\equiv i\pmod p$ ，其中 $0\leq i<n$ ，可以直接返回 $y_i$ .
  • 先求 $(n-1)!$ 的逆元，再倒序递推其他阶乘逆元，预处理需要 $O(n+\log p)$ 时间.

快速傅里叶变换#

多项式有两种常用的表示方式：

  • 系数表示：$f(x)=\sum_{i=0}^{n-1}a_ix^i$ .
  • 点值表示：在 $n$ 个不同的横坐标处，记录 $f(x)$ 的值.

系数表示便于加减，点值表示便于乘法.

设 $C(x)=A(x)B(x)$ ，则对任意 $x_k$ 均有：

$$C(x_k)=A(x_k)B(x_k)$$

因此，多项式乘法可以转化为：

$$\text{系数表示}\ \longrightarrow\ \text{点值表示}\ \longrightarrow\ \text{逐点相乘}\ \longrightarrow\ \text{系数表示}$$

直接求值和插值仍然较慢，需要选择一组具有特殊性质的点.

单位根#

方程 $x^n=1$ 在复数域中有 $n$ 个不同的根，称为 $n$ 次单位根.

记，

$$\omega_n=e^{\frac{2\pi\mathrm{i}}n}=\cos\frac{2\pi}n+\mathrm{i}\sin\frac{2\pi}n$$

其中 $\mathrm{i}^2=-1$ ，则所有 $n$ 次单位根为：

$$1,\omega_n,\omega_n^2,\dots,\omega_n^{n-1}$$

具有以下性质：

$$\omega_n^{k+n}=\omega_n^k$$

当 $n$ 为偶数时，

$$\omega_n^{k+n/2}=-\omega_n^k,\qquad \omega_n^{2k}=\omega_{n/2}^k$$

即，相隔 $n/2$ 的两个单位根互为相反数；所有单位根平方后，只剩下 $n/2$ 个不同的值.

离散傅里叶变换#

取 $n$ 为 $2$ 的幂，设，

$$f(x)=\sum_{j=0}^{n-1}a_jx^j$$

求出 $f(x)$ 在所有 $n$ 次单位根处的值：

$$y_k=f(\omega_n^k)=\sum_{j=0}^{n-1}a_j\omega_n^{kj},\qquad 0\leq k<n$$

这一变换称为离散傅里叶变换，即 DFT . 快速傅里叶变换，即 FFT ，是快速计算 DFT 的算法.

按系数下标的奇偶性拆分：

$$f_0(x)=\sum_{j=0}^{n/2-1}a_{2j}x^j,\qquad f_1(x)=\sum_{j=0}^{n/2-1}a_{2j+1}x^j$$

则，

$$f(x)=f_0(x^2)+xf_1(x^2)$$

对于 $0\leq k<n/2$ ，有：

$$\begin{aligned} f(\omega_n^k)&=f_0(\omega_{n/2}^k)+\omega_n^kf_1(\omega_{n/2}^k)\\ f(\omega_n^{k+n/2})&=f_0(\omega_{n/2}^k)-\omega_n^kf_1(\omega_{n/2}^k) \end{aligned}$$

故，只需递归求出两个规模为 $n/2$ 的 DFT ，再用 $O(n)$ 时间合并.

$$T(n)=2T(n/2)+O(n)=O(n\log n)$$

当 $n=1$ 时，多项式为常数，直接返回该系数.

逆变换#

单位根满足：

$$\sum_{k=0}^{n-1}\omega_n^{kt}= \begin{cases} n,&n\mid t,\\ 0,&n\nmid t. \end{cases}$$

当 $n\nmid t$ 时，由等比数列求和：

$$\sum_{k=0}^{n-1}\omega_n^{kt}=\frac{1-\omega_n^{nt}}{1-\omega_n^t}=0$$

因此，对于 $0\leq j<n$ ，

$$\begin{aligned} \sum_{k=0}^{n-1}y_k\omega_n^{-kj} &=\sum_{r=0}^{n-1}a_r\sum_{k=0}^{n-1}\omega_n^{k(r-j)}\\ &=na_j \end{aligned}$$

即，

$$a_j=\frac1n\sum_{k=0}^{n-1}y_k\omega_n^{-kj}$$

将单位根替换为其逆元，执行同样的 FFT ，最后将每一项除以 $n$ ，即可完成逆变换，即 IFFT .

多项式乘法#

设 $A(x),B(x)$ 分别有 $r,s$ 个系数，则乘积有至多 $r+s-1$ 个系数.

取满足 $n\geq r+s-1$ 的最小的 $2$ 的幂，将两个系数数组补零至长度 $n$ .

  • 分别对两个数组进行 FFT .
  • 将对应点值相乘，得到乘积多项式的点值.
  • 进行 IFFT ，取前 $r+s-1$ 项，即为乘积的系数.

时间复杂度为 $O(n\log n)$ ，空间复杂度为 $O(n)$ .

需要注意：

  • 补零长度必须足够，否则得到的是模 $x^n-1$ 意义下的乘积，即循环卷积.
  • 复数 FFT 存在浮点误差. 整数卷积通常将结果四舍五入，但只有误差小于 $1/2$ 时才能保证恢复正确整数.
  • 常见的迭代实现先进行二进制位逆序置换，再按 $2,4,8,\dots,n$ 的长度合并，每层使用对应长度的单位根.

快速数论变换#

FFT 利用复数域中的单位根，NTT 则利用模质数意义下的单位根.

所有运算均在模 $p$ 意义下进行，可以避免浮点误差.

原根与单位根#

设 $p$ 为质数. 若 $g$ 的幂能够遍历模 $p$ 的所有非零元素，则称 $g$ 为模 $p$ 的原根.

即，$g$ 的乘法阶为 $p-1$ ，满足：

$$g^t\equiv1\pmod p\iff(p-1)\mid t$$

若 $n\mid(p-1)$ ，令，

$$\omega_n=g^{\frac{p-1}{n}}\pmod p$$

则 $\omega_n$ 的阶恰为 $n$ . 因为，

$$\omega_n^t\equiv1\pmod p\iff(p-1)\mid\frac{p-1}{n}t\iff n\mid t$$

故 $1,\omega_n,\dots,\omega_n^{n-1}$ 两两不同，可以作为求值点.

对于奇质数 $p$ 和偶数 $n\mid(p-1)$ ，同样有：

$$\omega_n^{n/2}\equiv-1\pmod p,\qquad \omega_n^2\equiv\omega_{n/2}\pmod p$$

因此，FFT 中按奇偶下标拆分、递归求值和合并的过程，在这里仍然成立.

正变换与逆变换#

正变换为：

$$y_k\equiv\sum_{j=0}^{n-1}a_j\omega_n^{kj}\pmod p$$

同样利用单位根求和性质，可以得到逆变换：

$$a_j\equiv n^{-1}\sum_{k=0}^{n-1}y_k\omega_n^{-kj}\pmod p$$

其中，

$$n^{-1}\equiv n^{p-2}\pmod p,\qquad \omega_n^{-1}\equiv\omega_n^{p-2}\pmod p$$

即，将单位根换为其逆元，执行同样的变换，最后乘上 $n^{-1}$ .

多项式乘法的流程与 FFT 相同：补零、正变换、逐点相乘、逆变换.

对于长度为 $n$ 的变换，时间复杂度为 $O(n\log n)$ ，空间复杂度为 $O(n)$ .

模数的限制#

采用按奇偶拆分的算法时，需要 $n=2^k$ ，且 $n\mid(p-1)$ .

因此，常选择形如 $p=c\cdot2^s+1$ 的质数，使其支持长度不超过 $2^s$ 的二次幂变换.

常用模数为：

$$p=998244353=119\cdot2^{23}+1$$

其一个原根为 $g=3$ ，故支持的最大二次幂变换长度为 $2^{23}$ .

需要注意：

  • 补零后的长度既要不小于乘积的系数个数，也要满足 $n\mid(p-1)$ .
  • 长度为 $\ell$ 的合并使用 $g^{(p-1)/\ell}$ 作为单位根，逆变换使用它的逆元.
  • NTT 得到的是模 $p$ 的卷积结果. 若要求整数卷积，仅用一个模数可能无法恢复原值.
  • 若目标模数不支持所需长度，不能直接套用该 NTT . 可以在多个合适的质数下计算，再通过中国剩余定理合并；恢复整数后再取目标模数时，所用模数的乘积必须足以唯一确定真实系数.
  • 模乘使用足够宽的整数类型，模减后将结果调整到 $[0,p)$ .

多项式卷积与循环卷积#

设，

$$A(x)=\sum_{i=0}^{r-1}a_ix^i,\qquad B(x)=\sum_{j=0}^{s-1}b_jx^j$$

则，

$$C(x)=A(x)B(x)=\sum_{k=0}^{r+s-2}\left(\sum_{i+j=k}a_ib_j\right)x^k$$

即，普通卷积对应下标相加.

若只需要前 $n$ 项，则计算：

$$C(x)\equiv A(x)B(x)\pmod{x^n}$$

这里模 $x^n$ 表示舍去所有次数不小于 $n$ 的项.

而长度为 $n$ 的 DFT 中，求值点均满足 $x^n=1$ ，故无法区分 $x^k$ 与 $x^{k+n}$ .

正变换、逐点相乘、逆变换后，实际得到：

$$C(x)\equiv A(x)B(x)\pmod{x^n-1}$$

其系数为：

$$c_k=\sum_{i+j\equiv k\pmod n}a_ib_j$$

称为循环卷积.

因此，普通卷积需要补零至不小于 $r+s-1$ 的变换长度，保证高次项不会回绕到低次项.

特别地，即使只保留乘积的前 $n$ 项，也不能直接使用长度为 $n$ 的循环卷积代替. 一般先计算足够长度的普通卷积，再截断.

形式幂级数#

$$A(x)=\sum_{i=0}^{+\infty}a_ix^i$$

将 $x$ 看作形式符号，只关心每一项的系数，不要求代入某个数后收敛.

记，

$$[x^k]A(x)=a_k$$

则两个形式幂级数相等，当且仅当对应系数全部相等.

乘法定义为：

$$[x^k](A(x)B(x))=\sum_{i=0}^{k}a_ib_{k-i}$$

每一项只涉及有限次运算，因此不需要讨论无穷求和的收敛性.

在算法中，通常只计算前 $n$ 项，即模 $x^n$ 意义下的结果.

以下将精度为 $n$ 理解为已知 $0,1,\dots,n-1$ 次项，并记长度为 $n$ 量级的多项式乘法复杂度为：

$$M(n)=O(n\log n)$$

模质数 $p$ 运算时，涉及积分、$\ln$、$\exp$ 的常规算法取 $n\leq p$ ，使 $1,2,\dots,n-1$ 均可逆. NTT 的变换长度限制仍需单独满足.

多项式求逆#

给定 $A(x)$ ，求 $B(x)$ ，使得：

$$A(x)B(x)\equiv1\pmod{x^n}$$

存在逆元的充要条件为 $a_0\neq0$ . 这里系数在域上运算；一般环上则要求 $a_0$ 可逆.

比较常数项，有：

$$b_0=a_0^{-1}$$

比较 $k$ 次项，有：

$$b_k=-a_0^{-1}\sum_{i=1}^{k}a_ib_{k-i}$$

故逆元存在且唯一，但逐项计算需要 $O(n^2)$ 时间.

考虑倍增.

已知 $B(x)$ 满足：

$$A(x)B(x)\equiv1\pmod{x^m}$$

设误差 $E(x)=1-A(x)B(x)$ ，则 $x^m\mid E(x)$ ，从而 $x^{2m}\mid E(x)^2$ .

取，

$$B_{\mathrm{new}}(x)=B(x)(2-A(x)B(x))$$

则，

$$\begin{aligned} A(x)B_{\mathrm{new}}(x) &=A(x)B(x)(2-A(x)B(x))\\ &=(1-E(x))(1+E(x))\\ &=1-E(x)^2\\ &\equiv1\pmod{x^{2m}} \end{aligned}$$

故，

$$B_{\mathrm{new}}\equiv B(2-AB)\pmod{x^{2m}}$$

从 $B=a_0^{-1}$ 开始，每次将精度翻倍，直到达到 $n$ .

时间复杂度为：

$$O(M(1)+M(2)+M(4)+\cdots+M(n))=O(M(n))=O(n\log n)$$

每次只保留当前所需的系数；最后一次精度取 $\min(2m,n)$ 即可.

多项式求导与积分#

设，

$$A(x)=\sum_{i=0}^{n-1}a_ix^i$$

则，

$$A'(x)=\sum_{i=1}^{n-1}ia_ix^{i-1}$$

取积分常数为 $0$ ，有：

$$\int A(x)\,\mathrm{d}x=\sum_{i=0}^{n-1}\frac{a_i}{i+1}x^{i+1}$$

求导将系数乘上下标，再左移一位；积分将系数除以新下标，再右移一位.

时间复杂度均为 $O(n)$ ，积分需要相应整数的逆元.

模质数 $p$ 时，不能除以 $p$ 的倍数. 计算结果模 $x^n$ 只需积分到 $x^{n-1}$ ，因此只需 $1,2,\dots,n-1$ 可逆.

需要注意精度：已知 $A\pmod{x^n}$ ，只能确定 $A'\pmod{x^{n-1}}$ .

多项式牛顿迭代#

多项式求逆中的倍增，可以推广到方程求解.

设要解关于未知级数 $B$ 的方程：

$$F(B)=0$$

已知 $B$ 正确到模 $x^m$ ，设新的解为 $B+\Delta$ ，其中 $x^m\mid\Delta$ .

对于关于 $B$ 的多项式 $F$ ，展开得到：

$$F(B+\Delta)\equiv F(B)+F'(B)\Delta\pmod{x^{2m}}$$

因为所有含 $\Delta^2$ 的项均为 $x^{2m}$ 的倍数.

若 $F'(B)$ 可逆，则，

$$\Delta\equiv-\frac{F(B)}{F'(B)}\pmod{x^{2m}}$$

故，

$$B_{\mathrm{new}}\equiv B-\frac{F(B)}{F'(B)}\pmod{x^{2m}}$$

其中 $F'(B)$ 是对未知量 $B$ 求导，不是对 $x$ 求导. 对适用的形式幂级数函数，也可以在相应系数可除的截断精度内使用这一展开.

每次迭代能否进行，取决于初始解是否正确，以及 $F'(B)$ 的常数项是否可逆.

多项式对数#

给定 $A(x)$ ，其中 $A(0)=1$ ，求：

$$B(x)=\ln A(x)\pmod{x^n}$$

其常数项取 $B(0)=0$ .

由，

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

得到：

$$\ln A(x)\equiv\int\frac{A'(x)}{A(x)}\,\mathrm{d}x\pmod{x^n}$$

因此，依次进行求导、求逆、相乘、积分即可.

其中 $A'/A$ 只需要保留到模 $x^{n-1}$ .

时间复杂度为 $O(M(n))=O(n\log n)$ .

要求 $A(0)=1$ ，是为了使用常数项为 $0$ 的形式对数；在有限域中不能直接对任意非零常数取普通实数意义下的对数.

多项式指数#

给定 $A(x)$ ，其中 $A(0)=0$ ，求：

$$B(x)=\exp A(x)\pmod{x^n}$$

则 $B(0)=1$ ，且，

$$\ln B(x)=A(x)$$

令 $F(B)=\ln B-A$ ，则 $F'(B)=B^{-1}$ .

由牛顿迭代：

$$\begin{aligned} B_{\mathrm{new}} &\equiv B-\frac{\ln B-A}{B^{-1}}\\ &\equiv B(1+A-\ln B)\pmod{x^{2m}} \end{aligned}$$

从 $B=1$ 开始，每次将精度翻倍.

每轮求一次当前精度的 $\ln B$ ，再进行乘法，故总时间复杂度为 $O(M(n))=O(n\log n)$ .

特别地，每轮都只计算当前精度；若每轮均按最终长度计算，会多出不必要的开销.

多项式开方#

先考虑 $A(0)\neq0$ ，求：

$$B(x)^2\equiv A(x)\pmod{x^n}$$

初始值需要满足 $b_0^2=a_0$ . 模奇质数 $p$ 时，先求常数项的模平方根；若不存在，则多项式也不存在平方根.

令 $F(B)=B^2-A$ ，则 $F'(B)=2B$ .

故，

$$B_{\mathrm{new}}\equiv\frac12\left(B+\frac AB\right)\pmod{x^{2m}}$$

选定非零的 $b_0$ 后，逐次倍增，得到对应的唯一分支.

除求常数项模平方根外，时间复杂度为 $O(M(n))$ .

若 $A(0)=0$ ，设 $t<n$ 为第一个非零系数的下标：

$$A(x)=x^tC(x),\qquad C(0)\neq0$$
  • 若 $t$ 为奇数，则无解，因为平方后第一个非零项的次数必为偶数.
  • 若 $t=2s$ ，则先求 $D^2\equiv C\pmod{x^{n-2s}}$ ，再取 $B=x^sD$ .
  • 在模 $x^n$ 的条件下，$B$ 的 $n-s$ 次至 $n-1$ 次项不受约束，可以取 $0$ ，因此此时解不一定只有两个.
  • 若 $A\equiv0\pmod{x^n}$ ，可以直接取 $B=0$ .

上述迭代要求 $2$ 可逆，不适用于特征为 $2$ 的情形.

多项式快速幂#

给定非负整数 $k$ ，求：

$$B(x)\equiv A(x)^k\pmod{x^n}$$

当 $A(0)=1$ 时，

$$A(x)^k=\exp(k\ln A(x))$$

一般地，设 $t$ 为 $A$ 的第一个非零系数下标，$c=a_t\neq0$ ，则，

$$A(x)=cx^tD(x),\qquad D(0)=1$$

故，

$$A(x)^k=c^kx^{tk}\exp(k\ln D(x))$$

处理顺序为：

  • 若 $k=0$ ，结果取 $1$ .
  • 若 $k>0$ 且 $A\equiv0\pmod{x^n}$ ，结果为 $0$ .
  • 若 $tk\geq n$ ，结果为 $0$ .
  • 否则只需计算 $\exp(k\ln D)$ 的前 $n-tk$ 项，乘 $c^k$ 后右移 $tk$ 位.

时间复杂度为 $O(M(n)+\log k)$ ，其中 $\log k$ 来自常数项快速幂.

模质数 $p$ 时，需要区分：

  • 乘在 $\ln D$ 前的 $k$ ，使用 $k\bmod p$ .
  • 非零常数的幂 $c^k$ ，可以使用 $k\bmod(p-1)$ .
  • 判断 $tk\geq n$ 时，需要原指数的大小信息，不能使用取模后的指数.

以上 $\ln/\exp$ 方法沿用 $n\leq p$ 的条件. 普通的多项式二进制快速幂不依赖这一条件，复杂度为 $O(M(n)\log k)$ .

多项式除法与取模#

给定非零多项式 $B(x)$ ，求唯一的 $Q(x),R(x)$ ，使得：

$$A(x)=B(x)Q(x)+R(x),\qquad\deg R<\deg B$$

设 $\deg A=n,\deg B=m$ . 若 $n<m$ ，则 $Q=0,R=A$ .

否则，记 $k=n-m+1$ ，定义按指定次数翻转：

$$A^R(x)=x^nA(x^{-1}),\quad B^R(x)=x^mB(x^{-1}),\quad Q^R(x)=x^{n-m}Q(x^{-1})$$

则，

$$A^R(x)=B^R(x)Q^R(x)+x^nR(x^{-1})$$

因为 $\deg R\leq m-1$ ，所以 $x^nR(x^{-1})$ 的最低次数至少为 $n-m+1=k$ .

故，

$$Q^R(x)\equiv A^R(x)(B^R(x))^{-1}\pmod{x^k}$$

将得到的 $Q^R$ 按长度 $k$ 翻转，即得 $Q$ ，再计算：

$$R=A-BQ$$

由于 $B^R(0)$ 是 $B$ 的最高次非零系数，故在域上一定可逆.

时间复杂度为 $O(M(n+1))$ .

实现时先去除 $A,B$ 的高位零系数，确定实际次数；但恢复 $Q$ 时必须按指定长度 $k$ 翻转，不能随意删除占位的零.

多点求值#

给定次数小于 $n$ 的多项式 $A(x)$ 和 $n$ 个点 $x_0,x_1,\dots,x_{n-1}$ ，求所有 $A(x_i)$ .

直接代入需要 $O(n^2)$ 时间，考虑分治.

对区间 $[l,r)$ 定义：

$$P_{l,r}(x)=\prod_{i=l}^{r-1}(x-x_i)$$

叶子为 $P_{i,i+1}=x-x_i$ ，内部节点由左右子节点相乘得到，称为乘积树.

在每个节点维护：

$$R_{l,r}(x)=A(x)\bmod P_{l,r}(x)$$

因为子节点的多项式整除父节点的多项式，所以可以直接将父节点的余式继续对两个子节点取模.

到达叶子时，

$$R_{i,i+1}(x)=A(x)\bmod(x-x_i)=A(x_i)$$

即得到对应点值.

每层总规模为 $O(n)$ ，共有 $O(\log n)$ 层，故时间复杂度为 $O(M(n)\log n)=O(n\log^2 n)$ .

存储整棵乘积树需要 $O(n\log n)$ 空间. 多点求值允许横坐标重复；只有插值时才要求横坐标两两不同.

快速插值#

给定 $n$ 个横坐标两两不同的点 $(x_i,y_i)$ ，求次数小于 $n$ 的多项式 $A(x)$ .

设，

$$P(x)=\prod_{i=0}^{n-1}(x-x_i)$$

则，

$$P'(x_i)=\prod_{j\neq i}(x_i-x_j)$$

由拉格朗日插值：

$$A(x)=\sum_{i=0}^{n-1}\frac{y_i}{P'(x_i)}\cdot\frac{P(x)}{x-x_i}$$

先建立乘积树，求出 $P'$ ，再通过多点求值得到所有 $P'(x_i)$ .

记，

$$w_i=\frac{y_i}{P'(x_i)}$$

在区间 $[l,r)$ 维护：

$$F_{l,r}(x)=\sum_{i=l}^{r-1}w_i\prod_{\substack{l\leq j<r\\j\neq i}}(x-x_j)$$

叶子为 $F_{i,i+1}=w_i$ . 设中点为 $m$ ，则：

$$F_{l,r}=F_{l,m}P_{m,r}+F_{m,r}P_{l,m}$$

因为左半部分每一项还缺少右半部分的所有因子，右半部分同理.

递归合并后，根节点即为 $A(x)$ .

时间复杂度为 $O(M(n)\log n)=O(n\log^2 n)$ ，存储乘积树需要 $O(n\log n)$ 空间.

所有 $P'(x_i)$ 非零，可以利用前缀积和一次求逆，在线性次域运算内批量求出它们的逆元；无需对每个点分别快速幂.

任意模数卷积#

若目标模数 $q$ 不适合 NTT ，可以在多个适合 NTT 的质数下分别计算，再合并答案.

这里 $q$ 可以是合数，卷积本身不需要除法.

先将输入系数规范到 $[0,q)$ . 若两个数组长度分别为 $r,s$ ，则真实整数卷积系数满足：

$$0\leq c_k\leq\min(r,s)(q-1)^2$$

选取不同的 NTT 质数 $p_1,p_2,\dots,p_t$ ，令，

$$P=\prod_{i=1}^{t}p_i$$

分别求出 $c_k\bmod p_i$ . 若 $P>\min(r,s)(q-1)^2$ ，则这些余数能唯一确定真实整数 $c_k$ .

再对 $q$ 取模，即得答案.

中国剩余定理合并#

以三个质数为例，设某个系数的余数为 $r_1,r_2,r_3$ ，依次计算：

$$t_1=r_1$$
$$t_2\equiv(r_2-t_1)p_1^{-1}\pmod{p_2}$$
$$t_3\equiv(r_3-t_1-p_1t_2)(p_1p_2)^{-1}\pmod{p_3}$$

其中 $0\leq t_2<p_2,0\leq t_3<p_3$ .

则区间 $[0,P)$ 中唯一的解为：

$$c=t_1+p_1t_2+p_1p_2t_3$$

求 $c\bmod q$ 时，可以将各项直接在模 $q$ 意义下合并，避免显式保存完整的 $c$ .

需要注意：

  • 每个 $p_i$ 都必须支持所需的变换长度.
  • “使用三个模数”本身不能保证正确，仍需检查模数乘积与系数上界.
  • 若只确定了 $c\bmod P$ ，而真实系数可能超过 $P$ ，通常不能据此确定 $c\bmod q$ .
  • 若恢复有正有负、绝对值不超过 $B$ 的整数系数，需 $P>2B$ ，并将结果还原到对称区间.
  • 合并过程中的模乘仍需足够宽的整数类型，即使最终答案只对较小的 $q$ 取模.

固定使用常数个模数时，时间复杂度为 $O(n\log n)$ ，其中 $n$ 为补零后的变换长度.

拆系数#

若系数过大，可以取基数 $B$ ，写成：

$$a_i=a_{i,0}+Ba_{i,1},\qquad b_i=b_{i,0}+Bb_{i,1}$$

则，

$$a*b=a_0*b_0+B(a_0*b_1+a_1*b_0)+B^2(a_1*b_1)$$

将一次大系数卷积转化为若干次小系数卷积，再合并结果.

不够时继续拆成更多位. 使用复数 FFT 仍需控制误差；使用多模 NTT 则对拆分后每次卷积检查整数系数上界.

分治 FFT#

考虑形如以下形式的递推：

$$f_i=h_i+\sum_{j=0}^{i-1}f_jg_{i-j}$$

其中 $h_i,g_i$ 已知，$f_i$ 需要按顺序求出.

虽然右侧是卷积形式，但 $f$ 尚未全部确定，不能一开始直接对完整的 $f$ 做卷积.

考虑求解区间 $[l,r)$ ，取 $m=\lfloor(l+r)/2\rfloor$ ：

  • 先递归求出 $f_l,\dots,f_{m-1}$ .
  • 利用一次卷积，计算左半部分对右半部分的贡献.
  • 将贡献累加到右半部分，再递归求出 $f_m,\dots,f_{r-1}$ .

具体地，令：

$$U_t=f_{l+t},\qquad 0\leq t<m-l$$
$$V_t=g_t,\qquad 0\leq t<r-l$$

其中取 $g_0=0$ . 计算 $W=U*V$ ，则对于 $m\leq i<r$ ：

$$W_{i-l}=\sum_{j=l}^{m-1}f_jg_{i-j}$$

只将这些下标的结果累加到右半部分.

初始时令所有 $f_i=h_i$ . 递归过程中，进入某个区间前，更早区间对它的贡献已经累加；到达叶子时，该项即为最终值.

对于每一对 $j<i$ ，它们恰好在一个分治节点中分别属于左右两侧，故贡献不会遗漏，也不会重复.

每层卷积总开销为 $O(n\log n)$ ，共 $O(\log n)$ 层，故时间复杂度为 $O(n\log^2 n)$ .

临时数组用后释放或复用时，额外空间可以控制为 $O(n)$ . 使用 NTT 计算卷积时，也常称为分治 NTT .

特别地，上述最简单的固定卷积核递推，还可以直接使用生成函数：

$$F=H+FG\quad\Longrightarrow\quad F=\frac{H}{1-G}$$

其中 $G(0)=0$ ，利用多项式求逆即可做到 $O(n\log n)$ . 分治方法更适合需要按顺序确定状态，且跨区间贡献仍可写成卷积的递推.

线性递推与多项式取模#

已知 $d$ 阶线性递推：

$$f_n=c_1f_{n-1}+c_2f_{n-2}+\cdots+c_df_{n-d},\qquad n\geq d$$

以及初值 $f_0,f_1,\dots,f_{d-1}$ ，求 $f_N$ .

构造特征多项式：

$$C(x)=x^d-c_1x^{d-1}-c_2x^{d-2}-\cdots-c_d$$

在模 $C(x)$ 意义下，

$$x^d\equiv c_1x^{d-1}+c_2x^{d-2}+\cdots+c_d$$

其降幂规则与数列递推完全相同.

设，

$$x^N\equiv R(x)=\sum_{i=0}^{d-1}r_ix^i\pmod{C(x)}$$

则，

$$f_N=\sum_{i=0}^{d-1}r_if_i$$

证明如下：

定义线性映射 $L(x^i)=f_i$ . 对任意 $t\geq0$ ，由递推式：

$$L(x^tC(x))=f_{t+d}-\sum_{j=1}^{d}c_jf_{t+d-j}=0$$

又，$x^N-R$ 是 $C$ 的倍数，因此 $L(x^N-R)=0$ ，即得结论.

利用二进制快速幂计算 $x^N\bmod C$ ，每次乘法后立即取模，使次数保持小于 $d$ .

  • 朴素乘法与降幂：$O(d^2\log(N+1))$ .
  • 快速乘法与快速取模：$O(M(d)\log(N+1))$ .

当 $N=0$ 时直接返回 $f_0$ . 固定模多项式 $C$ 后，可以预处理翻转多项式的逆元，供每次取模复用.

若只有数列前若干项而未知递推式，还需要先寻找递推关系；这与已知递推式后求第 $N$ 项是两个不同的问题.

Bostan–Mori#

给定有理生成函数：

$$F(x)=\frac{P(x)}{Q(x)},\qquad Q(0)\neq0$$

求 $[x^N]F(x)$ . 先考虑 $\deg P<d,\deg Q\leq d$ ，系数在奇特征的域上运算.

分子分母同乘 $Q(-x)$ ：

$$\frac{P(x)}{Q(x)}=\frac{P(x)Q(-x)}{Q(x)Q(-x)}$$

记，

$$U(x)=P(x)Q(-x),\qquad V(x)=Q(x)Q(-x)$$

由于 $V(-x)=V(x)$ ，所以 $V$ 只含偶次项.

设，

$$U(x)=U_0(x^2)+xU_1(x^2),\qquad V(x)=V_0(x^2)$$

则，

$$[x^N]\frac{P(x)}{Q(x)}= \begin{cases} [x^{N/2}]\dfrac{U_0(x)}{V_0(x)},&N\text{ 为偶数},\\ [x^{(N-1)/2}]\dfrac{U_1(x)}{V_0(x)},&N\text{ 为奇数}. \end{cases}$$

即，每轮进行：

  • 计算 $U=PQ(-x)$ 和 $V=QQ(-x)$ .
  • 根据 $N$ 的奇偶性，保留 $U$ 的偶数下标项或奇数下标项，并将下标压缩一半.
  • 保留 $V$ 的偶数下标项，并将下标压缩一半.
  • 令 $N\leftarrow\lfloor N/2\rfloor$ .

每轮分母次数仍不超过 $d$ ，分子次数仍小于 $d$ ，而 $N$ 缩小一半.

当 $N=0$ 时，答案为：

$$\frac{P(0)}{Q(0)}$$

故时间复杂度为 $O(M(d)\log(N+1))$ ，额外空间为 $O(d)$ .

这里的奇偶指系数下标的奇偶；构造 $Q(-x)$ 时，仅将奇数次项的系数取负. 可以对照 Bostan–Mori 的实现核对这一轮变换.

用于线性递推#

对于，

$$f_n=\sum_{i=1}^{d}c_if_{n-i}$$

令，

$$Q(x)=1-c_1x-c_2x^2-\cdots-c_dx^d$$
$$P(x)\equiv Q(x)\left(\sum_{i=0}^{d-1}f_ix^i\right)\pmod{x^d}$$

则，

$$\sum_{i=0}^{+\infty}f_ix^i=\frac{P(x)}{Q(x)}$$

因为 $QF$ 的所有 $d$ 次及以上系数都由递推式抵消，而低于 $d$ 次的部分恰好为 $P$ .

故可以直接用 Bostan–Mori 求第 $N$ 项.

特征多项式 $C(x)$ 与生成函数分母 $Q(x)$ 满足：

$$C(x)=x^dQ(x^{-1})$$

两种算法使用的系数顺序不同，需要区分.

快速沃尔什变换#

普通卷积要求 $i+j=k$ . 若将下标运算替换为按位或、按位与、按位异或，则得到三种位运算卷积：

$$c_k=\sum_{i\mathbin{\mathrm{op}}j=k}a_ib_j$$

设数组长度为 $n=2^m$ ，下标均在 $[0,n)$ .

OI 中常将这三类快速变换统称为 FWT . 其中 XOR 使用 Walsh–Hadamard 变换，OR、AND 分别对应子集、超集上的 Zeta 变换.

它们的共同流程仍然是：变换、逐点相乘、逆变换.

按位或卷积#

将下标看作二进制集合，定义：

$$\widehat a_S=\sum_{T\subseteq S}a_T$$

则，

$$\begin{aligned} \widehat c_S &=\sum_{K\subseteq S}\sum_{I\cup J=K}a_Ib_J\\ &=\sum_{I\subseteq S}\sum_{J\subseteq S}a_Ib_J\\ &=\widehat a_S\widehat b_S \end{aligned}$$

因为 $I\cup J\subseteq S$ 当且仅当 $I\subseteq S$ 且 $J\subseteq S$ .

逐位处理时，设一对下标只在当前位不同，对应值为 $(u,v)$ ，其中 $u$ 的当前位为 $0$ ，$v$ 的当前位为 $1$ .

正变换：

$$(u,v)\longrightarrow(u,u+v)$$

逆变换：

$$(u,v)\longrightarrow(u,v-u)$$

对每一位都执行一次，即得到子集和及其逆变换.

按位与卷积#

定义超集和：

$$\widehat a_S=\sum_{T\supseteq S}a_T$$

因为 $I\cap J\supseteq S$ 当且仅当 $I\supseteq S$ 且 $J\supseteq S$ ，故同样有：

$$\widehat c_S=\widehat a_S\widehat b_S$$

正变换：

$$(u,v)\longrightarrow(u+v,v)$$

逆变换：

$$(u,v)\longrightarrow(u-v,v)$$

按位异或卷积#

先考虑一位下标：

$$c_0=a_0b_0+a_1b_1,\qquad c_1=a_0b_1+a_1b_0$$

则，

$$c_0+c_1=(a_0+a_1)(b_0+b_1)$$
$$c_0-c_1=(a_0-a_1)(b_0-b_1)$$

因此正变换取：

$$(u,v)\longrightarrow(u+v,u-v)$$

再做一次同样的变换，得到 $(2u,2v)$ ，故单层逆变换为：

$$(u,v)\longrightarrow\left(\frac{u+v}{2},\frac{u-v}{2}\right)$$

多位时对每一位分别处理. 也可以逆变换时不逐层除以 $2$ ，而在全部变换后统一除以 $n$ . 这一实现方式可对照 XOR 卷积与 Walsh–Hadamard 变换.

更一般地，定义：

$$\widehat a_S=\sum_T(-1)^{\operatorname{popcount}(S\mathbin{\&}T)}a_T$$

其中 $\operatorname{popcount}$ 表示二进制中 $1$ 的个数. 由于符号满足：

$$(-1)^{\operatorname{popcount}(S\mathbin{\&}(I\oplus J))} =(-1)^{\operatorname{popcount}(S\mathbin{\&}I)}(-1)^{\operatorname{popcount}(S\mathbin{\&}J)}$$

故异或卷积也被转化为逐点相乘.

三种变换的时间复杂度均为 $O(n\log n)$ ，可原地完成变换；保存输入和结果共需 $O(n)$ 空间.

需要注意：

  • 数组长度只需覆盖所有下标，并补齐到 $2$ 的幂；位运算后的下标仍在 $[0,n)$ ，不需要按普通卷积补到两倍长度.
  • OR、AND 的变换与逆变换仅用加减，不要求模数为质数.
  • XOR 的上述逆变换要求 $2$ 可逆. 模奇数时可以使用，模偶数时不能直接套用.
  • 单层运算的两个新值都由旧的 $(u,v)$ 计算，原地修改时需要暂存.
  • FWT 不需要单位根，也不需要 FFT 中的二进制位逆序置换.
  • OR 卷积允许两个集合相交；要求两个集合互不相交的子集卷积，不能直接用一次 OR 卷积代替.

积性函数#

若 $\text{gcd}(a,b)=1$ ，时有 $f(ab)=f(a)f(b)$ ，则 $f$ 为积性函数.

若对于任意正整数 $a,b$ 总有 $f(ab)=f(a)f(b)$ ，则 $f$ 为完全积性函数.

对于任意积性函数均有以下性质：

  • $f(1)=1$
  • $n=\prod{p_i^{e^i}},f(n)=\prod{{f(p_i^{e^i})}}$

特别地，对于完全积性函数有：

$n=\prod{p_i^{e^i}},f(n)=\prod{{f(p_i)}^{e^i}}$

以下讨论几种常见的积性函数及其特有性质：

恒等函数#

恒等函数是完全积性函数，定义为： $\text{I}(x)=1$

元函数#

元函数是完全积性函数，定义为： $\text{e}(x)=[x=1]$

单位函数#

单位函数是完全积性函数，定义为： $\text{id}(x)=x$

约数个数函数#

约数个数函数是积性函数，定义为： $\text{d}(x)=\sum_{i|x}1$

除数函数#

除数函数是积性函数，定义为：

$$\sigma_k(x)=\sum_{i|x}i^k$$

欧拉函数#

莫比乌斯函数#

莫比乌斯函数定义为：

$$\mu(x)= \begin{cases} 1, & n=1,\\ 0, & n \text{ is divisible by a square > 1},\\ (-1)^k, & n \text{ is the product of } k \text{ distinct primes}. \end{cases}$$

性质：

$$\sum_{d|n}\mu(d)=[n=1]$$

证明：

$$n=\prod_{i=1}^{k}{p_i^{e_i}},n'=\prod_{i=1}^k{p_i}$$
$$\sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)=\sum_{i=0}^k\binom{k}{i}(-1)^i=(1-1)^{k}=[k=0]=[n=1]$$

莫比乌斯反演#