为什么竞赛里要学多项式

收录内容#

多项式为什么值得学
系数表示 / 点值表示 / 插值
FFT / NTT 的使用直觉
形式幂级数在竞赛里的位置
什么时候该想到多项式

先把误区说在前面#

很多人第一次看到多项式算法，会直接被这些词吓住：

FFT
NTT
FWT
形式幂级数
多项式求逆 / ln / exp / sqrt

于是就容易把它理解成一坨“板子专区”。

但如果只把它当板子，通常会出现两个结果：

看过模板，题目里还是想不到；
记得操作名，却不知道为什么卷积会突然出现。

我现在更愿意这样记：

生成函数负责把问题装进系数；
多项式算法负责高效处理这些系数；
真正贯穿它们的关键词只有一个：卷积。

多项式先不是“算法”，而是一个容器#

把序列 $a_0,a_1,\dots,a_n$ 装进

A(x)=a_0+a_1x+\cdots+a_nx^n

以后，很多原本分散在序列上的操作，都会变成统一的代数运算。

最基础的三件事#

加法：逐项相加。
数乘：逐项乘常数。
乘法：卷积。

其中乘法最重要：

A(x)B(x)=\sum_{k\ge 0}\left(\sum_{i=0}^k a_i b_{k-i}\right)x^k

也就是说， $x^k$ 的系数恰好是序列卷积：

c_k = \sum_{i=0}^k a_i b_{k-i}

所以只要你在题里看到：

两部分独立贡献要合并；
按“和为 $k$ ”统计方案数；
每个状态由前面一整段状态卷起来；

本质上都已经很接近多项式乘法了。

为什么卷积这么常见#

卷积不是“多项式专属名词”，它在竞赛里出现得非常多。

典型场景#

两个集合元素和的分布统计；
方案数合并；
字符串匹配中的相关性计算；
一段 DP 的批量转移；
生成函数乘法；
形式幂级数运算的底层核心。

朴素卷积是 $O(n^2)$ 。规模小时当然够用，但一旦长度到 $10^5$ 级别，基本就必须想办法换表示了。

从系数表示切到点值表示#

这是多项式里最关键的视角切换。

系数表示#

我们平时写的就是系数表示：

A(x)=a_0+a_1x+\cdots+a_nx^n

优点：

容易建模；
加法很自然；
系数就是题目答案。

缺点：

乘法太慢，朴素就是 $O(n^2)$ 。

点值表示#

如果知道多项式在若干个点上的取值：

(x_0, A(x_0)), (x_1, A(x_1)), \dots, (x_n, A(x_n))

只要点够多，就能唯一确定这个次数不超过 $n$ 的多项式。

这时乘法会变得非常简单：

C(x)=A(x)B(x) \Rightarrow C(x_i)=A(x_i)B(x_i)

也就是说：

在系数域里，乘法难；
在点值域里，乘法只是逐点相乘。

所以整套 FFT / NTT 的思路，其实就是：

系数表示 $\to$ 点值表示；
逐点相乘；
点值表示 $\to$ 系数表示。

插值为什么重要#

前面这套流程之所以成立，本质上依赖一个事实：

一个次数不超过 $n$ 的多项式，被 $n+1$ 个不同点的函数值唯一确定。

这件事在竞赛里有两层含义：

做 FFT / NTT 时，需要把“点值表示”再插值回来；
很多题目本身就能通过“先求若干点值，再插值出整体式子”来做，这就是拉格朗日插值那条线。

所以多项式这块并不只是“乘法加速”，它还提供了一种非常实用的思维：

一个对象可能在不同表示下有完全不同的运算复杂度。

把多项式最常见的表示方式放一起看

系数表示：建模方便，乘法慢。
点值表示：乘法快，恢复需要插值。
拉格朗日插值：已知少量点值时，直接求某个点或者还原整体多项式。
形式幂级数表示：把“次数有限的多项式”推广成“只关心前若干项的无穷级数”。

FFT 到底在做什么#

FFT 不是一个新运算，而是快速计算 DFT（离散傅里叶变换）。

直觉版理解#

如果直接把多项式拿去若干点上求值，复杂度还是高。FFT 的妙处在于：

选一组非常特殊的点，也就是单位根；
借助它们的对称性，把一个大问题拆成两个小问题；
递归 / 迭代地完成求值与逆变换。

最经典的拆法就是偶数项和奇数项分治：

A(x)=A_{even}(x^2)+xA_{odd}(x^2)

当你在单位根上求值时，很多点会成对出现，递归结构自然就出来了。

为什么复杂度会降到 $O(n\log n)$ #

每一层把规模减半；
一共有 $\log n$ 层；
每层做线性量级的“蝴蝶操作”。

于是总复杂度就是 $O(n\log n)$ 。

FFT 的现实问题#

FFT 常在复数域做，竞赛里容易遇到：

精度误差；
四舍五入问题；
系数过大时的稳定性问题。

所以在模意义卷积里，更常用的是 NTT。

NTT：把 FFT 搬到有限域里#

NTT 的核心思路和 FFT 一样，只是把复数单位根换成模意义下的原根。

为什么 998244353 这么常见#

因为它满足：

998244353 = 119 \times 2^{23} + 1

这意味着它支持长度为 $2^k$ （ $k \le 23$ ）的单位根结构，非常适合做 NTT。

我做题时对 NTT 的关注点#

模数是不是形如 $c\cdot 2^k + 1$ ；
是否存在原根；
变换长度要补成 2 的幂；
正变换和逆变换的根要区分；
逆变换最后别忘了整体乘上长度的逆元。

一份常用的 NTT 骨架#

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 998244353;
constexpr int G = 3;

long long qpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void ntt(vector<int>& a, bool invert) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        long long wn = qpow(G, (MOD - 1) / len);
        if (invert) wn = qpow(wn, MOD - 2);
        for (int i = 0; i < n; i += len) {
            long long w = 1;
            for (int j = 0; j < len / 2; ++j) {
                int u = a[i + j];
                int v = (int)(w * a[i + j + len / 2] % MOD);
                a[i + j] = u + v < MOD ? u + v : u + v - MOD;
                a[i + j + len / 2] = u - v >= 0 ? u - v : u - v + MOD;
                w = w * wn % MOD;
            }
        }
    }

    if (invert) {
        long long inv_n = qpow(n, MOD - 2);
        for (int& x : a) x = (int)(x * inv_n % MOD);
    }
}

vector<int> convolution(vector<int> a, vector<int> b) {
    int need = (int)a.size() + (int)b.size() - 1;
    int n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);

    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; ++i) a[i] = (long long)a[i] * b[i] % MOD;
    ntt(a, true);

    a.resize(need);
    return a;
}

cpp

多项式不只会“乘”#

做到这里，如果只把它理解成卷积加速，还是有点窄。

在竞赛里，多项式后面通常会继续连到形式幂级数（FPS）。

形式幂级数可以干什么#

如果把

A(x)=a_0+a_1x+a_2x^2+\cdots

看成只关心前若干项的无穷级数，那么可以定义：

导数；
积分；
逆元；
对数；
指数；
开根。

这些操作听起来很“代数”，但竞赛里经常对应的是：

复杂递推的批量求解；
组合结构的封装；
一类题的统一处理接口。

为什么它们又会回到卷积#

因为这些高级操作最后往往都会落到：

若干次多项式乘法；
牛顿迭代；
导数 / 积分配合卷积。

所以真正的底座还是卷积。FFT / NTT 这一步不稳，后面的 FPS 也立不住。

什么时候该想到多项式#

这是我觉得最重要的一节。

信号 1：存在“大卷积”#

当你已经能把问题化成

c_k = \sum_{i=0}^k a_i b_{k-i}

而朴素复杂度又明显过不了时，多项式乘法就是第一候选。

信号 2：很多状态要统一平移 / 合并#

有些 DP 不是单个状态难，而是“每一层都要把整条序列卷一遍”。

这时如果把状态序列装进多项式里，问题会突然变得规整很多。

信号 3：题目在暗示“按值统计整段分布”#

比如：

两数组和的分布；
多项选择后的和分布；
匹配贡献按偏移量统计；
一类计数式需要批量求所有系数。

信号 4：已经出现生成函数#

如果前一步建模已经写出了生成函数，而你又发现“最终卡在乘法太慢”，那基本就已经走到多项式门口了。

学习顺序别反#

我现在更认可的顺序是：

先把卷积看懂；
再理解系数表示和点值表示的切换；
然后学 FFT / NTT；
最后再进形式幂级数。

如果反过来一上来背“多项式 ln/exp/sqrt 板子”，体验通常会非常差，因为你不知道自己到底在算什么。

做 NTT 时最容易出锅的地方

长度没补到 2 的幂。
模数和原根不匹配。
逆变换忘了乘 $n^{-1}$ 。
下标越界，尤其是 need = a.size() + b.size() - 1 这一步。
系数可能为负时，取模归一化没做好。
题目其实只需要朴素卷积，却硬上 NTT，反而把实现复杂化了。

我会怎么给这块定性#

多项式不是“炫技模板库”，它更像一种统一接口：

你先把问题变成系数；
再把对系数的操作变成代数运算；
最后用 FFT / NTT / FPS 去加速。

如果只是记板子，很容易忘；如果先看懂“为什么会变成卷积”，很多题就会自己露出多项式的味道。