2020-2021:teams:legal_string:jxm2001:多项式应用
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:多项式应用 [2020/10/20 17:44] jxm2001 |
2020-2021:teams:legal_string:jxm2001:多项式应用 [2021/08/29 18:56] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 多项式练习 1 ====== | + | ====== 多项式应用 ====== |
| ===== 习题一 ===== | ===== 习题一 ===== | ||
| 行 72: | 行 72: | ||
| </hidden> | </hidden> | ||
| - | ===== 习题二 ===== | + | ===== 习题二（字符串匹配） ===== |
| [[https://www.luogu.com.cn/problem/P4173|洛谷p4173]] | [[https://www.luogu.com.cn/problem/P4173|洛谷p4173]] | ||
| 行 201: | 行 201: | ||
| </hidden> | </hidden> | ||
| - | ===== 习题三 ===== | + | ===== 习题三（差分与前缀和） ===== |
| [[https://www.luogu.com.cn/problem/P5488|洛谷p5488]] | [[https://www.luogu.com.cn/problem/P5488|洛谷p5488]] | ||
| 行 319: | 行 319: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | |||
| + | ===== 习题四（矩阵卷积） ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 考虑快速计算序列 $\{C\}$，其中 $A_i,B_i$ 均为 $w\times w$ 矩阵 | ||
| + | |||
| + | $$ | ||
| + | C_i=\sum_{j=0}^i A_jB_{i-j}(0\le i\le n) | ||
| + | $$ | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 不难发现 $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)$。 | ||
| + | |||
| + | |||
2020-2021/teams/legal_string/jxm2001/多项式应用.1603187064.txt.gz · 最后更改: 2020/10/20 17:44 由 jxm2001
