110-数值算法-多项式插值

核心概述

多项式插值：给定 n 个互异点 (x_i, y_i) 构造次数 ≤ n−1 的唯一多项式 P 使 P(x_i)=y_i，常用拉格朗日或牛顿形式，并可在可用域下用 FFT/NTT 加速多点插值与变换。

原文引述

Description: Interpolate a polynomial of degree ≤ n−1 through points (x_i, y_i) with distinct x_i. Supports naive Lagrange O(n^2) and FFT/NTT-based O(n log^2 n) for special grids (e.g., consecutive or roots of unity). Time: O(n^2) naive; O(n log^2 n) for consecutive points via NTT Status: tested ——摘自本节点现有英文注释

展开阐述

• 函数/接口（据实现）

  • vector interpolate(const vector& x, const vector& y, ll mod)
    • 拉格朗日插值，返回系数表示的多项式（模 mod）。
  • vector interpolateConsecutive(const vector& y, ll mod)
    • 当 x_i=0,1,…,n−1 时的快速插值（用 NTT/NTT 的除法技巧）。
  • 依赖：088-数论-模逆、091-数论-模幂、099-数值算法-模域FFT（用于快速版本）。

• 拉格朗日插值（O(n^2)）

  • 公式：P(x) = Σ_{i=0}^{n-1} y_i · l_i(x)，其中 l_i(x) = ∏_{j≠i} (x−x_j)/(x_i−x_j)。
  • 实现：
    1. 预计算分母 denom[i] = ∏_{j≠i} (x_i−x_j) mod mod。
    2. 对每个 i：
       • 计算分子 numerator[i] = y_i · inv(denom[i]) mod mod。
       • 构造 l_i(x) 的系数：从常数项 1 开始，对每个 j≠i 乘 (−x_j) 并更新系数。
    3. 累加 P(x) = Σ numerator[i]·l_i(x)。
  • 优化：可先构造 L(x) = ∏ (x−x_i)，再求 L’(x_i) = ∏_{j≠i} (x_i−x_j) 以减少重复乘法。

• 快速插值（连续整数点，O(n log^2 n)）

  • 特殊情形 x_i = i（或等差数列）：
    1. 构造 F(x) = Σ y_i·∏_{j≠i} (x−j) = L(x)·Σ y_i / (x−i)。
    2. 在 NTT 中除以 (x−i) 可用“前缀/后缀乘法 + 取模”实现。
    3. 用 NTT 计算点值，再做逆变换得到系数。
  • 依赖：099-数值算法-模域FFT 的卷积与点值互转。

• 数值与实现注意

  • 模逆：所有除法改为乘逆元（见 088-数论-模逆）。
  • 溢出：乘法用 128 位或090-数论-长整型模乘。
  • 唯一性：若 x_i 有重复则插值不唯一；应先检查或报错。
  • 评估：得到系数后，可用 Horner 法在 O(n) 评估任意点值，或用 FFT/NTT 批量评估。

• 输出语义

  • 返回多项式系数向量 a，使 P(x) = Σ a[i]·x^i，满足 P(x_i)=y_i。

• 复杂度

  • 拉格朗日 O(n^2)；连续点快速版 O(n log^2 n)。

• 使用与注意

  • 若仅需求某单点值，可用拉格朗日直接计算 O(n) 而不构造系数。
  • 对大规模点集，优先检查 x_i 是否为等差数列或单位根，以用 FFT/NTT 加速。
  • 与多项式乘法/除法联动：插值常用于构造乘积/商的多项式（见 111-数值算法-多项式）。

关联节点

• 111-数值算法-多项式
• 099-数值算法-模域FFT
• 098-数值算法-快速傅里叶变换
• 088-数论-模逆
• 094-数论-模运算