半在线卷积

Nine_Suns · 2024-02-15 08:55:15 · 个人记录

在搞多项式题时，不免化出一些不易操作的式子，如 F'=F\cdot G+1 之类的，没办法套模板解决，半在线卷积可以在 O(n\log^2n) 内很好的解决它们。

半在线卷积实质上是强制中序遍历的 \rm cdq 分治。它的步骤大约是这样：

为了方便处理，首先将 n 补足至 2 的次幂。

设正在处理的区间是 [l,r),mid=\frac {l+r}2，那么应先递归处理 [l,mid)，再处理 [l,mid) 对 [mid,r) 的贡献，最后处理 [mid,r)。

接下来通过几个问题知道半在线卷积的具体方法。

对于 F_n=\sum\limits_{i=0}^{n}F_iG_{n-i}，其中 F_0=1,G_0=0。

设正在处理的区间是 [l,r),mid=\frac {l+r}2。先递归处理 [l,mid)，此时 [l,mid) 的 F 的值均已算出，我们用 F_{[l,mid)} 卷上 G_{[0,r-l)}，并将得到的多项式 [mid,r) 项的值累加到 F 中。这就处理了 [l,mid) 对 [mid,r) 的贡献。然后递归处理 [mid,r) 即可。

复杂度 O(n\log^2n)。

一个值得注意的地方是，在用 F_{[l,mid)} 卷 G_{[0,r-l)} 时，是一个 \frac {r-l}2 次多项式卷 r-l 次多项式的操作，由于 \rm NTT 是循环卷积，若在 r-l 的范围内直接卷，最后的 \frac {r-l}2 次会破坏掉前面的 \frac {r-l}2 次，而我们只需 [mid,r) 项的值，正好是没有被破坏的那部分，于是可以用 r-l 为范围卷，节省一部分常数。