分类 算法小结 下的文章

膜拜 $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。