laok 发布的文章

膜拜 $gg & EI & cy

半在线卷积大概是说$f_i=c_i(\sum_{j=1}^i f_{i-j}g_j)$这样的递推式

大家都会用分治fft $O(n\log^2 n)$计算对吧。

大概是,拆成两段,先算左边,然后一次fft算出左边对右边的贡献,然后算右边。

考虑每次拆成b段,然后算每两段之间的贡献。(这里认为每段长度相等)

算贡献看上去要做b^2次卷积,但是实际上记录下每一段的点值和转移数列的点值就只需要做$O(b)$次$DFT$了。

复杂度大概是$T(n)=bT(\frac{n}{b})+O(nb)+O(n\log \frac{n}{b})$

当$b=\log n$的时候复杂度是$O(\frac{n\log^2n}{\log \log n})$

实现细节:

一般b取4,8或者16比较快。

分块的时候可以优先前几段取2^x,这样方便直接fft不用浪费长度 而且方便记忆化转移数组的点值序列。

实际运行效率比传统分治fft写法快了很多

代码

实际效率确实也吊打传统分治fft。

早就有迁移到动态博客的想法,不过太鸽了

由于我用的是Arch Linux,一次滚动把nodejs滚到v14,然后hexo就坏了...

想了想不如干脆迁移到typecho,反正我也有国内主机。

文章大概都迁移过来了/cy

不过你想访问原来版本可以走https://old.qaq-am.com/

link

题意:有一个包含O,H,C的串,你现在只知道长度,每次可以询问一个串t在这个串里的所有出现位置,代价是$\frac{1}{|t|^2}$,你需要用不超过1.4的代价询问出这个串。

- 阅读剩余部分 -