多项式简介

多项式在数学和 OI 竞赛中都有着重要应用。在数学领域，多项式是由变量和系数通过有限次加、减、乘运算得到的代数式。在 OI 竞赛中，我们重点关注多项式的各种运算和变换，以解决实际问题。快速傅里叶变换（FFT）和快速数论变换（NTT）是多项式运算中的核心算法。

FFT 通过将多项式从系数表示转换为点值表示，利用复数的性质实现高效的多项式乘法运算，将时间复杂度从 \(O(n^2)\) 大幅降低到 \(O(n \log n)\)。

NTT 则是在模意义下的快速傅里叶变换，它利用数论中的原根等概念，避免了 FFT 中复数运算带来的精度问题，同样实现了高效的多项式乘法。这些多项式运算和变换算法在解决如卷积计算、多项式快速幂、生成函数等问题中发挥着重要作用，为解决复杂的数学计算和算法问题提供了有力工具。