当前位置：首页 > news >正文

NTT 及多项式学习笔记

news 2026/5/12 9:06:08

本文主要参考 NTT与多项式全家桶 -command_block。

NTT

概述

NTT 是一个将多项式由系数表达变化为点值表达的变换，类似 FFT。

NTT 的特点是求出的值在模某个质数意义下。

下文假定读者已经学会 FFT，如果不会请移步FFT 学习笔记一文。

分析

考虑我们已经知道的 FFT，其核心原理是利用单位根 $w$。那能不能找一个替代品呢？

考虑单位根有哪些性质：

$w_n^k=(w_n^1)^k$；
$\forall_{i\neq j,i,j\in[0,n)}w_n^i\neq w_n^j$；
$w_n^k=w_n^{k\bmod n}$；
$w_{2n}^{2k}=w_n^k$；

然后科学家们找到了一个叫原根的东西。接下来是数论小课堂（如果你已经知道相关知识，可以跳过本段剩余内容）：称 $a$ 在模 $p$ 意义下的阶是最小的整数 $k$，满足 $a^k \equiv 1 \pmod p$。如果 $a$ 与 $p$ 互质，那么认为 $a$ 的阶是正无穷，或不存在。阶可以理解为是幂的循环节长度。称满足在模 $p$ 意义下的阶等于 $\varphi(p)$ 的整数 $g$ 为原根。可以理解原根为可以在模 $p$ 意义下，将任意与 $p$ 互质的数表示为自己的幂。

那么回到这里，对于一个质数 $p$ 和其原根 $g$，$g$ 的阶数恰好为 $p-1$。同时注意到 $g^k$ 的阶数等于 $(p-1)/\gcd(k,p-1)$。因此只要当 $n\mid (p-1)$ 时，$g^{(p-1)/n}$ 的阶数恰好为 $n$，并满足了所有性质。

但是怎么保证条件成立呢？因为在 FFT 前要把多项式的长度补到 $2$ 的若干次幂，所以只需要找一个含 $2$ 这个质因数尽可能多的质数即可，$998244353=2^{23}\times 7\times 17 +1$ 就很好，并且它还有原根，为 $3$。

那么直接把 FFT 中的单位根换成 $g^{(p-1)/n}$ 即可。

分治NTT/半在线卷积

引入

这又是什么？~~众所周知~~，多项式乘法有另一个名字：多项式和卷积。就是在 $W=F*G$ 这个卷积中， $F[i]$ 和 $G[j]$ 会贡献到 $W[i+j]$。

和卷积的形式比较常见，比如看下面这个问题（来自 P4721）：

给定序列 $g_{1\dots n - 1}$，求序列 $f_{0\dots n - 1}$。其中 $f_i=\sum_{j=1}^if_{i-j}g_j$，边界为 $f_0=1$。对 $998244353$ 取模。

显然，每一项都可以用 NTT 单独做一次，但是这样太浪费时间了，所以就有人提出了分治 NTT。

分析

如果你学过 cdq 分治，那么分治 NTT 和它类似。

设当前分治区间为 $[l,r]$，以此进行以下操作：

先求出 $[l,mid]$ 的 $f$；
然后计算 $[l,mid]$ 对 $[mid+1,r]$ 的贡献；
最后算 $[mid+1,r]$ 的 $f$。

对于第二步，记第 $i$ 项被贡献的数值为 $h_i$，那么有：

\[h_j=\sum_{i=l}^{mid}f_ig_{j-i} \]

和卷积，用 NTT 加速，主定理一算发现时间复杂度是 $O(n\log^2 n)$。

多项式的若干运算

基本的加减，数乘，和上文着重展开的乘法就不赘述了。

逆元

记 $F(x)G(x)=1$，其中 $F(x)$ 已知。

首先可以用分治 NTT 做。

但是这里用一种之后更为常用的办法：倍增法。

Fun Fact：$F(x) \bmod x^1=F(x)[0]$。显而易见。那么此时可以直接对常数项求逆元。

不妨假设已经求出了 $G'(x) \equiv F(x) \pmod {x^{n/2}}$。此时也有 $G(x)\equiv G'(x) \pmod {x^{n/2}}$。然后开始推式子：

\[\begin{aligned} G(x)&\equiv G'(x) &\pmod {x^{n/2}}\\ G(x)-G'(x)&\equiv 0&\pmod {x^{n/2}}\\ (G(x)-G'(x))^2&\equiv0&\pmod {x^n}\\ G^2(x)-2G(x)G'(x)+G'^2(x)&\equiv 0 &\pmod{x^n}\\ G(x)-2G'(x)+G'^2(x)F(x)&\equiv 0&\pmod{x^n}\\ G(x)&\equiv2G'(x)-G'^2(x)F(x) &\pmod{x^n}\end{aligned} \]

时间复杂度为 $O(n\log n)$。

常数优化：

首先，观察出上述递推过程中对复杂度影响最大的是 $G'^2(x)F(x)$ 的两次卷积。

关于 NTT 的一个重要知识：$NTT$ 本质上是长度为 $2^k$ 的循环和卷积。

这就是在说对 $i$ 次项系数的贡献会被贡献到 $i \bmod 2^k$ 次项系数。

然后又知道本题中其实在从 $\dfrac{n}{2}$ 倍增到 $n$ 时可以只算出 $i\in [\dfrac{n}{2},n)$ 次项的系数。

那么不妨先进行一次长度为 $n$ 的卷积 $F'(x)=G'(x)F(x)$，此时得到的多项式的 $[0,\dfrac{n}{2})$ 次项系数和 $[\dfrac{n}{2},n)$ 次项系数分别对应实际上应该得到的多项式的 $[n,\dfrac{3n}{2})$ 次项系数和 $[\dfrac{n}{2},n)$ 次项系数。

因为 $[n,\dfrac{3n}{2})$ 次项系数在这次倍增中不关心，那么就清空其对应位置的值。

那么不妨先进行一次长度为 $n$ 的卷积 $G'(x)F'(x)$，此时得到的多项式的 $[\dfrac{n}{2},n)$ 次项系数就对应实际上应该得到的多项式的 $[\dfrac{n}{2},n)$ 次项系数。

这样就把原本两次长度为 $2n$ 的卷积变成了两次长度为 $n$ 的卷积，理论上可以有 $\dfrac{1}{4}$ 的常数。

求导与积分

这和一般函数的求导与积分是一样的：

$F(x)$ 的导数为 $\sum \limits_{i=0}^{n-1}F[i+1]x^i$；
$F(x)$ 的积分为 $C+\sum \limits_{i=1}^n\dfrac{F[i-1]x^{i}}{i}$。

牛顿迭代

定义多项式复合为 $G(F(x))=\sum_{i=0}G[i]F(x)^i$。

这是什么？（多项式中的）牛顿迭代是解决以下问题：已知 $G$ 并且 $G(F(x))=0$，求 $F \pmod {x^n}$。

这里先给出结论，记 $F_0$ 表示 $G(F_0(x))\equiv 0 \pmod{x^{n/2}}$：

\[F(x)\equiv F_0(x)-\dfrac{G(F_0(x))}{G'(F_0(x)))} \pmod{x^n} \]

证明：

首先先来了解以下泰勒展开，记 $F^{(n)}(i)$ 表示 $F$ 的 $n$ 阶导数。如果已知在 $x_0$ 处 $F(x)$ 的值，那么以下式子恒成立：

\[F(x)=\sum_{i=1}\dfrac{F^{(i)}(x_0)}{i!}(x-x_0)^i \]

那么考虑 $F(x)$ 一定满足 $G(F(x)) \equiv 0 \pmod{x^{n/2}}$，因此有 $F(x) \equiv F_0(x) \pmod {x^{n/2}}$。那么不妨在模 $x^n$ 意义下展开 $G(F_0(x))$：

\[\begin{aligned} G(F(x))&\equiv G(F_0(x))+\sum_{i=1}\dfrac{G^{(i)}(F_0(x))}{i!}(F(x)-F_0(x))^i &\pmod {x^n}\\ &\equiv G(F_0(x))+\dfrac{G'(F_0(x))}{1!}(F(x)-F_0(x)) &\pmod{x^n}\\ F(x)&\equiv F_0(x)-\dfrac{G(F_0(x))}{G'(F_0(x))} &\pmod{x^n} \end{aligned} \]

证毕。

特别地，因为 $G(F_0(x))$ 的前 $\dfrac{n}{2}$ 位是 $0$，因此分母的精度只需要到 $\pmod {x^{n/2}}$ 即可。