多项式基础

What · 是什么

多项式基础是形式幂级数理论及所有多项式算法（FFT/NTT、求逆、ln/exp、开方、多点求值、拉格朗日反演等）的地基。核心概念：多项式环 R[x] 与形式幂级数环 R[[x]]（系数序列视角）；次数 deg f；乘法（系数卷积，FFT/NTT 加速到 O(n log n)）；复合 f∘g；形式导数与不定积分（逐项求导/积分）；乘法逆元（常数项非零存在，牛顿迭代 O(n log n)）；带余除法与模多项式（q、r 的唯一性）；常见的幂级数展开式（e^x、ln(1+x)、(1+x)^a、三角/反三角）；生成函数。

Why · 为什么

How · 实现

伪代码

# 核心操作一览
乘:    c = conv(a,b)                 # 卷积, NTT O(n log n)
导数:  df[i-1] = i*a[i]
积分:  it[i] = a[i-1]/i (i>=1)
逆元:  inv(f, n) 牛顿迭代 O(n log n)
带余除: q = rev(rev(f) * inv(rev(g)) mod x^{n-m+1}); r = f - q*g
求值:  Horner O(n) 单点

Python 实现

MOD = 998244353


def poly_mul(a, b, mod=MOD):
    """朴素多项式乘法(教学版)。O(nm)。"""
    res = [0] * (len(a) + len(b) - 1)
    for i, x in enumerate(a):
        if x == 0:
            continue
        for j, y in enumerate(b):
            res[i + j] = (res[i + j] + x * y) % mod
    return res


def poly_add(a, b, mod=MOD):
    n = max(len(a), len(b))
    res = [(a[i] if i < len(a) else 0) + (b[i] if i < len(b) else 0) for i in range(n)]
    return [x % mod for x in res]


def poly_sub(a, b, mod=MOD):
    n = max(len(a), len(b))
    res = [((a[i] if i < len(a) else 0) - (b[i] if i < len(b) else 0)) % mod for i in range(n)]
    return res


def poly_derivative(a, mod=MOD):
    """形式导数 f'(x)。"""
    return [(i * a[i]) % mod for i in range(1, len(a))]


def poly_integral(a, mod=MOD):
    """形式不定积分(取 0 常数项). 需要模逆元预计算。"""
    n = len(a) + 1
    inv = [0] * n
    inv[1] = 1
    for i in range(2, n):
        inv[i] = (mod - mod // i) * inv[mod % i] % mod
    return [0] + [a[i - 1] * inv[i] % mod for i in range(1, n)]


def poly_evaluate(a, x, mod=MOD):
    """Horner 求值。"""
    r = 0
    for c in reversed(a):
        r = (r * x + c) % mod
    return r


def poly_naive_inverse(a, n, mod=MOD):
    """多项式逆元 O(n^2)(教学版): f0 != 0 时存在。a 可不足 n 项(高位视为 0)。"""
    aa = a[:] + [0] * (n - len(a))
    inv0 = pow(aa[0], mod - 2, mod)
    res = [inv0]
    for i in range(1, n):
        s = 0
        for k in range(i):
            s = (s + res[k] * aa[i - k]) % mod
        res.append((-inv0 * s) % mod)
    return res


def poly_naive_division(f, g, mod=MOD):
    """带余除法 f = q*g + r (系数从低到高), deg(g)<=deg(f)。O(n^2)。"""
    f = f[:]
    g = g[:]
    n, m = len(f), len(g)
    if n < m:
        return [], f[:]
    inv_lead = pow(g[-1], mod - 2, mod)
    q = [0] * (n - m + 1)
    for i in range(n - 1, m - 2, -1):
        coef = f[i] * inv_lead % mod
        pos = i - m + 1
        q[pos] = coef
        for j in range(m):
            f[pos + j] = (f[pos + j] - coef * g[j]) % mod
    return q, f[:m - 1]


def poly_compose_naive(f, g, n, mod=MOD):
    """多项式复合 f(g(x)) 前 n 项, O(n^2)。"""
    res = [0] * n
    cur = [1]
    for c in f:
        if c:
            for i in range(len(cur)):
                if i < n:
                    res[i] = (res[i] + c * cur[i]) % mod
        # cur = cur * g
        new = [0] * min(n, len(cur) + len(g) - 1)
        for i in range(len(cur)):
            if cur[i] == 0:
                continue
            for j in range(len(g)):
                if i + j < n:
                    new[i + j] = (new[i + j] + cur[i] * g[j]) % mod
        cur = new
    return res


if __name__ == "__main__":
    import random
    for _ in range(100):
        n = random.randint(1, 8)
        m = random.randint(1, 8)
        f = [random.randint(0, 9) for _ in range(n)]
        g = [random.randint(0, 9) for _ in range(m)]
        # 乘法: (f*g) 系数
        prod = poly_mul(f, g)
        prod2 = [0] * (n + m - 1)
        for i, x in enumerate(f):
            for j, y in enumerate(g):
                prod2[i + j] = (prod2[i + j] + x * y) % MOD
        assert prod == prod2
        # 带余除法回代: f = q*g + r
        if len(f) >= len(g) and g[-1] % MOD != 0:
            q, r = poly_naive_division(f, g)
            back = poly_add(poly_mul(q, g), r + [0] * (len(f) - len(r)))
            assert back[:len(f)] == f
    # 多项式逆元: (1 - x)^{-1} = 1 + x + x^2 + ...
    inv = poly_naive_inverse([1, MOD - 1], 6)
    assert inv == [1, 1, 1, 1, 1, 1], inv
    # 导数与积分
    f = [1, 2, 3, 4]
    df = poly_derivative(f)
    assert df == [2, 6, 12]
    it = poly_integral([2, 6, 12])  # 积分(常数项取 0)
    assert it == [0, 2, 3, 4]
    # 导积分还原(去常数项)
    assert poly_derivative(it) == [2, 6, 12]
    print("polynomial-basics tests passed")

易错点

• 逆元存在性条件(常数项非零)忽略
• 卷积长度/补零错误导致结果截断
• 形式导数的常数项消失, 积分后再求导常数丢失
• 复合运算要求内层常数项为 0(否则项数无穷)
• 幂级数展开盲目代入非收敛域(数值问题)

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/poly/intro/
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/math/poly/intro.md
• CP-Algorithms✓ https://cp-algorithms.com/algebra/polynomial.html