基于Rollup定理的多项式乘法等价性证明 本文深入探讨了数论变换(NTT)在多项式乘法中的应用,通过Rollup定理证明了将多项式从系数形式转换为点值形式、进行点乘、再逆变换的步骤与直接Rollup等价。文章详细推导了数学过程,展示了如何利用NTT将乘法复杂度从O(n²)降至O(n log n),并强调了正交性在证明中的关键作用。 数论变换 卷积定理 多项式乘法 快速傅里叶变换 根的单位 正交性 RareSkills 发布于 2026-06-17 38 0 0