为什么竞赛里要学多项式

收录内容#

多项式为什么值得学
系数表示 / 点值表示 / 插值
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 去加速。

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

参考#

实战题解#

题目1: 大数乘法 (FFT基础应用)#

题目描述: 给定两个非负整数A和B,求A×B的结果。

数据范围: A和B的位数不超过10^5

思路分析:

暴力做法: 模拟竖式乘法,时间复杂度O(n²)

优化思路:

将数字的每一位看作多项式的系数
例如: 123 = 1×10² + 2×10¹ + 3×10⁰ 对应多项式 1x² + 2x + 3
两个数相乘 = 两个多项式相乘 = 卷积
使用FFT加速卷积,时间复杂度O(n log n)

完整代码:

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

const double PI = acos(-1.0);

struct Complex {
    double r, i;
    Complex(double r = 0, double i = 0) : r(r), i(i) {}
    Complex operator+(const Complex& b) const {
        return Complex(r + b.r, i + b.i);
    }
    Complex operator-(const Complex& b) const {
        return Complex(r - b.r, i - b.i);
    }
    Complex operator*(const Complex& b) const {
        return Complex(r * b.r - i * b.i, r * b.i + i * b.r);
    }
};

void FFT(vector<Complex>& a, int n, int inv) {
    if (n == 1) return;

    for (int i = 0, j = 0; i < n; i++) {
        if (i > j) swap(a[i], a[j]);
        for (int k = n >> 1; (j ^= k) < k; k >>= 1);
    }

    for (int len = 2; len <= n; len <<= 1) {
        Complex wn(cos(2 * PI / len), inv * sin(2 * PI / len));
        for (int i = 0; i < n; i += len) {
            Complex w(1, 0);
            for (int j = 0; j < len / 2; j++) {
                Complex u = a[i + j];
                Complex v = w * a[i + j + len / 2];
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w = w * wn;
            }
        }
    }

    if (inv == -1) {
        for (int i = 0; i < n; i++) a[i].r /= n;
    }
}

string multiply(string num1, string num2) {
    int n1 = num1.size(), n2 = num2.size();
    int n = 1;
    while (n < n1 + n2) n <<= 1;

    vector<Complex> a(n), b(n);
    for (int i = 0; i < n1; i++) a[i].r = num1[n1 - 1 - i] - '0';
    for (int i = 0; i < n2; i++) b[i].r = num2[n2 - 1 - i] - '0';

    FFT(a, n, 1);
    FFT(b, n, 1);

    for (int i = 0; i < n; i++) a[i] = a[i] * b[i];

    FFT(a, n, -1);

    vector<int> result(n);
    for (int i = 0; i < n; i++) result[i] = (int)(a[i].r + 0.5);

    for (int i = 0; i < n - 1; i++) {
        result[i + 1] += result[i] / 10;
        result[i] %= 10;
    }

    int pos = n - 1;
    while (pos > 0 && result[pos] == 0) pos--;

    string ans;
    for (int i = pos; i >= 0; i--) ans += char(result[i] + '0');
    return ans;
}

cpp

性能对比:

暴力: O(10^10) - 超时
FFT: O(10^5 log 10^5) ≈ 0.5秒

踩坑记录:

忘记位逆序置换
逆变换忘记除以n
进位处理时数组越界

题目2: 多项式求逆 (洛谷P4238)#

题目描述: 给定多项式f(x),求g(x)使得f(x)g(x) ≡ 1 (mod x^n)

思路: 牛顿迭代 + 倍增

递推公式: g(x) = 2g₀(x) - f(x)g₀²(x)
复杂度: T(n) = T(n/2) + O(n log n) = O(n log n)

踩坑: 模数998244353的原根是3

题目3: 生成函数计数#

问题: n种物品,第i种有a[i]个,重量为i。求装满容量m的方案数。

建模:

第i种物品生成函数: 1 + x^i + x^(2i) + … + x^(a[i]×i)
答案 = 所有生成函数乘积中x^m的系数

优化: NTT加速多项式乘法

朴素DP: O(nm²) - 超时
生成函数+NTT: O(nm log m) - 通过