2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛68
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛68 [2020/08/29 12:34] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛68 [2020/08/29 12:37] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 147: | 行 147: | ||
| ==== 题解 3 ==== | ==== 题解 3 ==== | ||
| - | 设 $F={x_0,x_1\cdots x_{n-1}}G=\{c,a\cdots b}$。 | + | 设 $F=\{x_0,x_1\cdots x_{n-1}\},G=\{c,a,0\cdots 0,b\}$。 |
| 于是所求答案为 $FG^k$ 的长度为 $n$ 的循环卷积。 | 于是所求答案为 $FG^k$ 的长度为 $n$ 的循环卷积。 | ||
| - | 直接暴力卷积复杂度 $O(n\log n\log k)$， | + | 直接暴力卷积时间复杂度 $O(n\log n\log k)$，如果套用 $\text{Bluestein's Algotithm}$ 时间复杂度 $O(n(\log n+\log k))$。 |
2020-2021/teams/legal_string/jxm2001/contest/牛客练习赛68.1598675688.txt.gz · 最后更改: 2020/08/29 12:34 由 jxm2001
