半在线卷积的O(nlog^2/loglogn)算法

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