3.【计算】多项式操作-1

半在线卷积¶

给出一个长度为 \(n\) 的序列 \(g\)，求长度为 \(n\) 的序列 \(f\) 满足

\[ f_i=R\qty(n,\sum_{j=0}^{i-1}f_jg_{i-j}) \]

其中 \(R(n,t)\) 是一个关于 \(n\) 和 \(t\) 的函数。

考虑 \(2\) 叉分治，我们的目的是，递归到每个叶子节点 \([k,k+1)\) 时，该叶子节点的值都已经变为

\[ \sum_{j=0}^{k-1}f_jg_{k-j} \]

假设当前求解的区间为 \([l,r)\)，而 \(m=\left\lfloor\frac{l+r}{2}\right\rfloor\)，\([l,m)\) 的答案已经计算出来，现在计算 \([m,r)\) 的答案，而 \(k\in [m,r)\)，那么该叶子的值可以分为

\[ t_k = \sum_{i=0}^{k-1} f_i g_{k-i} = \underbrace{\sum_{i=0}^{l-1} f_i g_{k-i}}_{\text{A: 更早区间的贡献}} + \underbrace{\sum_{i=l}^{mid-1} f_i g_{k-i}}_{\text{B: 左半区间的贡献}} + \underbrace{\sum_{i=mid}^{k-1} f_i g_{k-i}}_{\text{C: 右半区间内部的贡献}} \]

这里，我们可以假设 \(\text{A}\) 的部分已经被叠加到 \(t_k\) 上了，我们只需要在每次分治中把 \(\text{B}\) 部分叠加上去，将 \(\text{C}\) 部分留给接下来的分治中计算。

而这个 \(\text{B}\) 部分就是一个卷积，直接 NTT 即可。时间复杂度 \(\mathcal O(\textsf{M}(n)\log n)\)。

如果做 \(B\) 叉分治的话就可以优化到 \(\mathcal O\qty(\frac{\textsf{M}(n)\log n}{\log \log n})\)，推导略，考虑实现：

按大小 \(d\) 分块，假设区间 \([l,r)\) 被分为 \(\ell\) 块，标号从零开始。\(k\in [l+pd,\min\{l+(p+1)d,r\})\)（也就是 \(k\) 在第 \(p\) 块）。

\[ t_k=\underbrace{\sum_{i=0}^{l-1} f_i g_{k-i}}_{\text{A: 更早区间的贡献}}+\underbrace{\sum_{i=l}^{l+d-1}f_{i}g_{k-i}+\cdots +\sum_{i=l+(p-1)d}^{l+pd-1}f_{i}g_{k-i}}_{\text{B：这一段的贡献，第 }0\sim p-1\text{ 块}}+\underbrace{\sum_{i=l+pd}^{k-1}f_{i}g_{k-i}}_{\text{C：未来的贡献}} \]

中间的部分无非是 \(f\) 中取一段，\(g\) 中取一段，NTT 之后加到 \(k\) 这里来，也并不难。

到这里就可以直接实现了，接下来是一些卡常数的手法：

\(r-l\) 比较小的时候直接用半在线卷积那条原始的式子做 \(\mathcal O(n^2)\) 的暴力。
注意到假设 \(k\) 在块 \(p\)，现在计算 \(\text{B}\) 中的第 \(q\) 个求和号（也就是和 \([l+qd,l+(q+1)d)\) 卷积）

那么用到的 \(g\) 只和 \(p-q\) 相关，与当前正在哪个 \(p\) 无关，也就是 \(k-i\in [(p-q-1)d,(p-q+1)d)\)

所以我们这里可以不用做 \(\mathcal O(\ell^2)\) 次 NTT，把每个 \([l+sd,l+(s+2)d)\) 提出来，做 \(\mathcal O(\ell )\) 次就够了。

由 \(2\) 中进一步，每个求和号中，\(f\) 的区间长度是 \(d\)，\(g\) 的长度是 \(2d\)（每个 \(f\) 对应的 \(g\) 有限）

提出来做卷积之后，我们只关心卷积结果中的区间 \([d,2d)\)。

这里的道理也很简单，同样假设 \(k\) 在 \(p\) 块，\(i\) 在 \(q\) 块，那么

\(k\in [l+pd, l+(p+1)d)\)
\(i\in [l+qd,l+(q+1)d)\)
\(k-i\in [(p-q-1)d,(p-q+1)d)\)

拿来卷积的序列中，\(f\) 中的 \(a\) 就是 \(i-(l+qd)\)，\(g\) 中的 \(b\) 就是 \(k-i-(p-q-1)d\)，\(a+b<d\) 移项得 \(k<l+pd\)，因此这部分我们不要。

对高次部分的分析同理，所以结果序列中可能的 \(k\in [d,2d)\)。

对两个序列卷积的长度本来应该是 \(2d+d-1=3d-1\)，但是考虑到 NTT 做的是循环卷积，我们做 \(2d\) 长度的循环卷积，溢出部分是 \([2d,3d)\)，刚好加到 \([0,d)\) 里面，和我们的答案不冲突。因此，我们只需要做长度为 \(2d\) 的循环卷积即可。