「POI2018 R3」多项式 Polynomial 题解

题目分析

我们有一个 $n$ 次多项式：

$$W(x) = a_0 + a_1x + a_2x^2 + \cdots + a_{n-1}x^{n-1} $$

需要在 $n$ 个点 $q^1, q^2, \ldots, q^n$ 处求值，其中：

• $n$ 是 $2$ 的幂
• $q^n \equiv 1 \pmod{m}$

关键性质

由于 $q^n \equiv 1 \pmod{m}$，序列 $\{q^i \bmod m\}$ 是周期为 $n$ 的：

$$q^{i+n} \equiv q^i \cdot q^n \equiv q^i \pmod{m}$$

数学推导

问题重述

我们需要计算：

$$S = \sum_{k=1}^n W(q^k) \bmod m$$

和

$$W(q^k) = \sum_{j=0}^{n-1} a_j q^{kj} \bmod m \quad \text{for } k=1,\ldots,n $$

利用循环性质

由于 $q^n \equiv 1 \pmod{m}$，我们可以将指数模 $n$：

$$q^{kj} \equiv q^{kj \bmod n} \pmod{m}$$

定义序列 $b_r = \sum_{j \equiv r \pmod{n}} a_j$（实际上 $j < n$，所以就是 $a_r$），那么：

$$W(q^k) = \sum_{r=0}^{n-1} b_r q^{kr} \bmod m$$

这看起来像是一个离散傅里叶变换（DFT）的形式。

算法设计

方法1：直接计算（小数据）

对于 $n \leq 2^{10}$，可以直接计算：

def direct_method(n, m, q, a):
    # 预处理 q 的幂次
    q_pow = [1] * (n + 1)
    for i in range(1, n + 1):
        q_pow[i] = (q_pow[i-1] * q) % m
    
    # 计算每个点的值
    values = []
    total = 0
    for k in range(1, n + 1):
        val = 0
        for j in range(n):
            val = (val + a[j] * pow(q_pow[k], j, m)) % m
        values.append(val)
        total = (total + val) % m
    
    return total, values

时间复杂度：$O(n^2)$，适用于子任务1

方法2：利用FFT思想（大数据）

由于 $n$ 是 $2$ 的幂且 $q^n \equiv 1 \pmod{m}$，我们可以使用快速傅里叶变换的思想。

关键观察

令 $\omega = q$，则 $\omega^n \equiv 1 \pmod{m}$，且：

$$W(\omega^k) = \sum_{j=0}^{n-1} a_j \omega^{kj}$$

这正是多项式 $W(x)$ 在单位根 $\omega^k$ 处的取值，可以用快速数论变换（NTT）计算。

算法步骤

1. 验证模数：检查 $m$ 是否支持 NTT（需要存在原根）
2. 找到原根：如果 $m$ 是质数，找到模 $m$ 的原根 $g$
3. 计算变换：执行 NTT 将系数表示转换为点值表示

def ntt_method(n, m, q, a):
    # 检查 m 是否为质数且存在原根
    if not is_prime(m):
        # 如果 m 不是质数，需要使用其他方法
        return fallback_method(n, m, q, a)
    
    # 找到原根 g
    g = find_primitive_root(m)
    
    # 由于 q^n ≡ 1 mod m，q 应该是 g 的某次幂
    # 即 q ≡ g^k mod m，其中 k = (m-1)/n 的倍数
    
    # 执行 NTT
    values = ntt(a, n, m, g)
    
    # 调整顺序（NTT 输出顺序需要调整）
    total = sum(values) % m
    return total, values

方法3：Chirp Z-变换

对于更一般的情况，可以使用 Chirp Z-变换：

$$W(q^k) = q^{-k^2/2} \sum_{j=0}^{n-1} (a_j q^{-j^2/2}) \cdot q^{(k+j)^2/2} $$

这样就把问题转化为了卷积形式。

实现细节

部分分策略

题目提到：如果和正确但单个值错误，能得 40% 分数。

这意味着我们可以：

1. 先专注于高效计算总和 $S$
2. 总和可能比单个值更容易计算

总和的计算技巧

$$S = \sum_{k=1}^n W(q^k) = \sum_{k=1}^n \sum_{j=0}^{n-1} a_j q^{kj} = \sum_{j=0}^{n-1} a_j \sum_{k=1}^n q^{kj} $$

内层求和是等比数列：

$$\sum_{k=1}^n q^{kj} = \begin{cases} n & \text{if } q^j \equiv 1 \pmod{m} \\ \dfrac{q^{j(n+1)} - q^j}{q^j - 1} & \text{otherwise} \end{cases}$$

但由于 $q^n \equiv 1 \pmod{m}$，有 $q^{j(n+1)} \equiv q^j \pmod{m}$，所以：

• 如果 $q^j \equiv 1$，和为 $n$
• 否则，分子为 $0$，和为 $0$

因此：

$$S = n \cdot \sum_{j: q^j \equiv 1 \pmod{m}} a_j$$

由于 $q^n \equiv 1$，满足 $q^j \equiv 1$ 的 $j$ 是 $n$ 的约数。

最终算法

对于大数据（$n \leq 2^{20}$）

1. 计算总和：

   $$S = n \cdot \sum_{d|n} a_d \bmod m$$

2. 计算单个值：

   • 如果 $m$ 是质数且存在合适的原根，使用 NTT
   • 否则，使用 Chirp Z-变换或分治算法

代码框架

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

vector<long long> polynomial_evaluation(int n, long long m, long long q, vector<long long>& a) {
    // 1. 计算总和
    long long total = 0;
    for (int d = 0; d < n; d += n / __gcd(n, d)) {
        total = (total + a[d]) % m;
    }
    total = (total * (n % m)) % m;
    
    // 2. 计算每个点的值（使用合适的算法）
    vector<long long> values(n);
    if (n <= 1024) {
        // 小数据：直接计算
        for (int k = 0; k < n; k++) {
            long long val = 0, q_pow = 1;
            for (int j = 0; j < n; j++) {
                val = (val + a[j] * q_pow) % m;
                q_pow = (q_pow * q) % m;
            }
            values[k] = val;
        }
    } else {
        // 大数据：使用 NTT 或 Chirp Z-变换
        values = advanced_evaluation(n, m, q, a);
    }
    
    return {total, values};
}

复杂度分析

• 总和计算：$O(n)$
• 直接计算：$O(n^2)$，适用于 $n \leq 2^{10}$
• NTT/Chirp Z-变换：$O(n \log n)$，适用于 $n \leq 2^{20}$

总结

算法标签：数论、多项式、快速傅里叶变换、离散数学

本题的关键在于利用 $q^n \equiv 1 \pmod{m}$ 的循环性质和 $n$ 是 $2$ 的幂的特点，将多项式求值问题转化为离散傅里叶变换问题，从而使用快速算法在 $O(n \log n)$ 时间内解决。

对于不同的数据范围，需要采用不同的策略：

• 小数据：直接计算
• 大数据：NTT 或 Chirp Z-变换
• 总和计算：利用数论性质简化