简介
- 解决多项式中在等比数列处的多点求值问题。
- 时间复杂度 \(n \log_2 n + m \log_2 n\) 。
算法
以 P6800 【模板】Chirp Z-Transform - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 为例。
考虑 \(P(c^m)\) 这一项。
\[P(c^m) = \sum_{i = 0}^{n} a_ic^{im} \\
= \sum_{i = 0}^{n} a_ic^{\binom{i + m}{2} - \binom{i}{2} - \binom{m}{2}} \\
= c^{-\binom{m}{2}}\sum_{i = 0}^{n}(a_ic^{-\binom{i}{2}})c^{\binom{i + m}{2}}
\]
设 \(F(x) = \sum_{i = 0}^{n}a_ic^{- \binom{i}{2}}\) ， \(G(x) = \sum_{i = 0}^{n + m}c^{\binom{i}{2}}\)
把 \(F(x)\) 翻转以后和 \(G(x)\) 卷积, 往左边平移 \(n\) 位就是要求的多项式。