「多项式多点求值」题解

题意简化

给定 $n$ 次多项式：

$$f(x) = \sum_{i=0}^{n-1} a_i x^i$$

和 $n$ 个点：

$$x_k = b \cdot c^{4k} + d \cdot c^{2k} + e, \quad k=0,1,\dots,n-1 $$

要求计算 $f(x_0), f(x_1), \dots, f(x_{n-1})$，模 $M = 10^6+3$。

核心观察

直接对每个 $x_k$ 暴力计算 $f(x_k)$ 是 $O(n^2)$，$n \leq 60000$ 不可行。

关键点：

1. $x_k$ 有特殊形式：$x_k = b \cdot (c^{2k})^2 + d \cdot c^{2k} + e$
2. 设 $y_k = c^{2k}$，则 $x_k = b y_k^2 + d y_k + e$
3. $y_k$ 构成等比数列：$y_k = (c^2)^k$

优化思路

方法：利用多项式复合和快速求值

1. 定义新多项式： 令 $y = c^{2k}$，则 $x = b y^2 + d y + e$ 是一个二次函数。

2. 多项式复合： 我们实际上需要计算：

   $$f(g(y)) \quad \text{其中} \quad g(y) = b y^2 + d y + e $$

3. 快速多点求值： 已知 $y_k = (c^2)^k$ 是等比数列，对于多项式 $h(y) = f(g(y))$，我们需要计算：

   $$h(y_0), h(y_1), \dots, h(y_{n-1})$$

   其中 $y_k = r^k$，$r = c^2$。

4. 利用卷积： 如果 $h(y) = \sum_{i=0}^{2n-2} h_i y^i$，那么：

   $$h(r^k) = \sum_{i=0}^{2n-2} h_i r^{ki}$$

   这可以看作两个序列的卷积：

   $$h(r^k) = \sum_{i=0}^{2n-2} h_i \cdot (r^k)^i$$

5. Chirp Z-transform（CZT）： 计算 $h(r^0), h(r^1), \dots, h(r^{n-1})$ 正是CZT变换，可以用FFT在 $O(n\log n)$ 完成。

算法步骤

1. 计算 $g(y) = b y^2 + d y + e$
2. 多项式复合：计算 $h(y) = f(g(y))$，即把 $f(x)$ 中的 $x$ 替换为 $g(y)$
   • 由于 $g(y)$ 是二次，$h(y)$ 的次数是 $2(n-1)$
   • 可以用多项式复合的算法，或直接展开
3. 多点求值：计算 $h(r^0), h(r^1), \dots, h(r^{n-1})$，其中 $r = c^2$
   • 使用CZT变换，$O(n\log n)$
4. 输出结果

复杂度

• 多项式复合：$O(n\log n)$
• CZT变换：$O(n\log n)$
• 总复杂度：$O(n\log n)$，可过 $n=60000$

注意事项

• 模数 $M=10^6+3$ 是质数，可用NTT
• 注意 $c^k$ 的快速幂计算
• 边界情况：$b=0$ 时 $g(y)$ 是一次函数，更简单