半在线卷积的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。