CVBB ACM Team

--- 2020-2021:teams:legal_string:jxm2001:多项式应用 [2021/08/29 18:48]
jxm2001 ↷ 页面名由2020-2021:teams:legal_string:jxm2001:多项式练习_1改为2020-2021:teams:legal_string:jxm2001:多项式应用
+++ 2020-2021:teams:legal_string:jxm2001:多项式应用 [2021/08/29 18:56] (当前版本)
jxm2001 [题解]
@@ 行 332: / 行 332: @@
 ==== 题解 ====
-不难发现 $c_{ij}=\sum_{k=1}^w a_{ik}b_{kj}$，于是 $c_{ij}$ 可以拆分成 $w$ 个卷积。总时间复杂度 $O\left(w^3n\log n\right)$。
+不难发现 $c_{ij}=\sum_{k=1}^w a_{ik}b_{kj}$，于是 $c_{ij}$ 可以拆分成 $w$ 个卷积。
+考虑 $O\left(w^2n\log n\right)$ 预处理出 $\{a_{ij}\}$ 和 $\{b_{ij}\}$ 的 $\text{DFT}$ 结果。然后通过  $c_{ij}=\sum_{k=1}^w a_{ik}b_{kj}$ 可以 $O\left(w^3n\right)$ 计算每个 $\{c_{ij}\}$ 的 $\text{DFT}$ 结果。
+最后对每个 $\{c_{ij}\}$ 做 $\text{IDFT}$，总时间复杂度 $O\left(w^2n\log n+w^3n\right)$。