多项式的基础概念

在数学和计算机科学中，多项式是一类重要的代数结构。本文将介绍多项式的表示方法、相关运算以及高效计算这些运算的算法。

表示方法

一个 (n) 次多项式 (f(x)) 通常被表示为 (f(x) = \sum_{i=0}^{n-1} c_i x^i)。除了这种系数表示法外，还可以通过点值表示法来描述多项式。给定 (n) 个互不相同的点 ((x_i, y_i))，可以唯一确定一个 (n) 次多项式。这种表示方式有助于进行插值等操作。

离散卷积

离散卷积是两个函数 (f) 和 (g) 的一种组合形式，定义为 (h(n) = \sum_{i+j=n} f(i)g(j))。对于多项式乘法而言，其本质就是系数序列的加法卷积。

---

拉格朗日插值法

拉格朗日插值是一种有效的多项式插值方法，能够在 (O(n^2)) 时间内完成。假设已知 (n) 个点值 ((x_i, y_i))，可以通过构造 (n) 个辅助多项式 (g_i(x)) 来求解目标多项式 (f(x))。每个 (g_i(x)) 满足 (g_i(x_i) = y_i) 且 (g_i(x_j) = 0)（当 (j \neq i)）。最终结果为 (f(x) = \sum_{i=0}^{n-1} g_i(x))。

---

快速傅里叶变换 (FFT)

快速傅里叶变换是实现多项式乘法的核心工具之一，它能将时间复杂度从 (O(n^2)) 降低到 (O(n \log n))。

分治实现 FFT

分治思想是 FFT 的核心。通过将多项式拆分为奇次项和偶次项，递归地处理子问题，最终合并结果。代码如下：

void fft(std::vector<std::complex<double>>& a, bool inverse) {
    int n = a.size();
    if (n == 1) return;

    std::vector<std::complex<double>> even(n / 2), odd(n / 2);
    for (int i = 0; i < n / 2; ++i) {
        even[i] = a[2 * i];
        odd[i] = a[2 * i + 1];
    }

    fft(even, inverse);
    fft(odd, inverse);

    double angle = 2 * M_PI / n * (inverse ? -1 : 1);
    std::complex<double> w(1), wn(cos(angle), sin(angle));
    for (int i = 0; i < n / 2; ++i) {
        std::complex<double> t = w * odd[i];
        a[i] = even[i] + t;
        a[i + n / 2] = even[i] - t;
        if (inverse) {
            a[i] /= 2;
            a[i + n / 2] /= 2;
        }
        w *= wn;
    }
}

非递归实现 FFT

为了提高效率，可以采用非递归的方式实现 FFT。关键在于位逆序置换和蝴蝶操作。

void fft_non_recursive(std::vector<std::complex<double>>& a, bool inverse) {
    int n = a.size();
    for (int i = 0, j = 0; i < n; ++i) {
        if (i > j) std::swap(a[i], a[j]);
        int bit = n >> 1;
        while (j >= bit) {
            j -= bit;
            bit >>= 1;
        }
        j += bit;
    }

    for (int len = 2; len <= n; len <<= 1) {
        double angle = 2 * M_PI / len * (inverse ? -1 : 1);
        std::complex<double> wlen(cos(angle), sin(angle));
        for (int i = 0; i < n; i += len) {
            std::complex<double> w(1);
            for (int j = 0; j < len / 2; ++j) {
                std::complex<double> u = a[i + j], v = a[i + j + len / 2] * w;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w *= wlen;
            }
        }
    }

    if (inverse) {
        for (int i = 0; i < n; ++i) a[i] /= n;
    }
}

---

数论变换 (NTT)

数论变换是基于模意义下的整数域实现的 FFT。常用的模数如 (998244353) 满足特定条件，允许高效的计算。

const int MOD = 998244353, G = 3;
long long power(long long base, long long exp) {
    long long res = 1;
    while (exp > 0) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

void ntt(std::vector<long long>& a, bool inverse) {
    int n = a.size(), logn = 0;
    while ((1 << logn) < n) ++logn;

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

    long long root = power(G, (MOD - 1) / n);
    if (inverse) root = power(root, MOD - 2);
    for (int len = 2; len <= n; len <<= 1) {
        long long wlen = power(root, n / len);
        if (inverse) wlen = power(wlen, MOD - 2);
        for (int i = 0; i < n; i += len) {
            long long w = 1;
            for (int j = 0; j < len / 2; ++j) {
                long long u = a[i + j], v = a[i + j + len / 2] * w % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                w = w * wlen % MOD;
            }
        }
    }

    if (inverse) {
        long long inv_n = power(n, MOD - 2);
        for (int i = 0; i < n; ++i) a[i] = a[i] * inv_n % MOD;
    }
}

---

应用实例

多项式乘法

利用 FFT 或 NTT 可以高效地计算两个多项式的乘积。

半在线卷积

通过 CDQ 分治将在线问题转化为离线问题，从而解决形如 (f_i = \sum_{j=1}^i f_{i-j} g_j) 的递推关系。

多项式求逆

给定多项式 (f(x))，求 (g(x)) 使得 (f(x)g(x) \equiv 1 \pmod{x^n})。

void poly_inverse(const std::vector<long long>& a, std::vector<long long>& b, int n) {
    if (n == 1) {
        b = {power(a[0], MOD - 2)};
        return;
    }
    poly_inverse(a, b, (n + 1) / 2);
    int m = 1; while (m < 2 * n) m <<= 1;
    std::vector<long long> tmp_a(a.begin(), a.begin() + n), tmp_b(b.begin(), b.end());
    tmp_a.resize(m, 0), tmp_b.resize(m, 0);
    ntt(tmp_a, false), ntt(tmp_b, false);
    for (int i = 0; i < m; ++i) tmp_b[i] = (2 - tmp_a[i] * tmp_b[i] % MOD + MOD) % MOD * tmp_b[i] % MOD;
    ntt(tmp_b, true);
    b.resize(n);
    for (int i = 0; i < n; ++i) b[i] = tmp_b[i];
}