"在线"卷积全解-从cdq分治到多叉与自迭代结构
假定与引入
不妨让我们呆在一个可以 \(O(1)\) 计算且便于 \(dft\) 的域上(如 \(F_{998244353}\))
半在线卷积形如
已知序列 \(\{f\}\), 求 \(\{fg\}\) 但 \(g_n\) 仅在 \((fg)_{n-1}\) 被
计算出后才给出
另一个形式是已知序列 \(\{f\},\{h\}\), 求 \(\{g\}\) 满足 \(g_n=h_n\sum\limits_{i=0}^{n-1}g_if_{n-i}\)
虽然后一个形式并没有直观体现“在线”的特点(而且实际问题不一定长这样), 但这个形式有其他的好处, 可以在下文感受到.
全在线卷积形如
求 \(\{fg\}\) 但 \(f_n, g_n\) 仅在 \((fg)_{n-1}\) 被计算出后才给出
贡献图解
为了便于理解下面所讲解的内容, 这里先解释如何理解所谓的 "贡献图"
以长度为 8 的卷积图为例
此处应该有图
图上坐标为\((f_x,g_y)\) 的点对应 \(f_x \times g_y\), 卷积得到的 \((fg)_i\) 就是对斜线 \(x+y=i\) 求和.
那么我们的半在线计算过程就是
计算红色部分(\(x+y=0\))的和得到 \((fg)_0\) 进而得到 \(g_1\) 的值(如果是全在线此时才会得到 \(f_1\) 的值)
计算黄色部分(\(x+y=1\))的和得到 \((fg)_1\) 进而得到 \(g_2\) 的值(如果是全在线此时才会得到 \(f_2\) 的值)
计算浅绿色部分(\(x+y=2\))的和得到 \((fg)_2\) 进而得到 \(g_3\) 的值(如果是全在线此时才会得到 \(f_3\) 的值)
省略...
计算橙色(\(x+y=6\))的和得到 \((fg)_{6}\) 进而得到 \(g_{7}\) 的值(如果是全在线此时才会得到 \(f_{7}\) 的值)
计算米黄色(\(x+y=7\))的和得到 \((fg)_7\)
双向规约
半在线卷积和全在线卷积是容易双向规约的.
首先全在线卷积显然严格强于半在线卷积, 因此我们的问题实际上就是全在线卷积如何归约到半在线卷积
可以考虑一个倍增的思路, 检查其贡献形式.
此处应该有图
由图可以发现, 不妨设全在线卷积复杂度为 \(T_l\), 半在线卷积复杂度为 \(T_s\)
可以规约为 \(T_l(n) = T_l(n/2) + O(n\log n) + 2T_s(n/2)\)
显然半在线卷积不会弱于卷积, 所以我们不妨假设其复杂度 \(T_s(n)\ge O(n\log n), T_s(n) \ge 2T_s(n/2)\)
故原式可以写为 \(T_l(n) = T_l(n/2) + T_s(n)\) 显然这不会超过 \(2T_s(n)\) 故这两个东西同阶, 如果半在线卷积能以 \(T(n)\) 的复杂度解决则全在线卷积同样可以.
因此下面主要讲半在线卷积如何做.
cdq分治
拆成两段, 先算左边, 然后算左对右的贡献, 然后算右边.
其贡献图解也就是
此处应该有图
其复杂度为 \(T(n)=2T(n/2)+O(n\log n)\)
解得 \(T(n)=O(n\log^{2}n)\)
值得注意的是, 使用 \(dft\) 的乘法是循环卷积, 而我们注意到我们贡献的形式是长 \(2n\) 的序列卷上长 \(n\) 的序列然后提取后半部分, 那我们的 \(dft\) 长度只需要做到 \(2n\) 因为溢出的部分我们正好不要, 这对之后的做法至关重要.
多叉分治
能不能再给力一点啊?
我们注意到 \(dft\) 之后的点值形式容易计算之间的贡献, 只要最后 \(idft\) 就好了.
考虑拆成 \(B\) 段, 每次计算前面的段对本段的贡献, 然后算本段, 不难发现这样我们会做 \(O(B)\) 次长度为 \(O(n/B)\) 的 \(dft\) 和 \(idft\) 以及 \(O(B^2)\) 次长度为 \(O(n/B)\) 的点乘.
其贡献图解也就是
此处应该有图
(更具体的, 参考图解, 一般来说是 \(2B-2\) 次长度 \(2n/B\) 的 \(dft\) 以及其一半次数的 \(idft\) 以及 \(\dfrac{B(B-1)}{2}\) 次长度为 \(2n/B\) 的点乘)
因此复杂度为 \(T(n)=BT(n/B)+O(nB)+O(n\log n)\)
解得 \(B=\log n\) 此时有 \(T(n)=O(\dfrac{n\log^2n}{\log \log n})\)
自迭代结构
能不能再给力一点啊?
回顾上一张图, 我们惊奇的发现块之间的贡献同样是一个半在线卷积的形式/惊奇/惊奇/惊奇
那么块之间的贡献我们可以同样用一个半在线卷积跑, 这是一个自递归的结构, 有点类似区间静态半群查询.
这里的跑的块是 \(dft\) 之后的点值, 因为这样之间的乘法才能做到 \(O(len)\)
考虑到我们在 cdq 部分提及的循环卷积问题, 这部分每块的长度就是 \(2n/B\)
复杂度是 \(T(n)=BT(n/B)+(2n/B)T(B)+O(n\log n)\) .
一个可能的平衡是取 \(B=\sqrt n\) 这样就有 \(T(n) = 3T(\sqrt n)+O(n \log n)\), 解得 \(T(n) = O(n\log^{\frac{log 3}{log 2}}n)\)
但显然原式两支并不平衡, 所以我们可以直接在这个式子上做的更好 (ps:我没太看懂eiblog后半段(和原论文,嘤嘤嘤)在干嘛,按我的理解可以直接对着这个式子再做)
令 \(l = log(n)\)
设\(H(l)=T(n)/n\)
\(H(n)=H(n-b)+2H(b)+O(n)\)