社论「不 CDQ 的分治 NTT」(详细揭秘)

· · 个人记录

这里「CDQ 分治 NTT」指的是（半）在线卷积，用这个名字仅是区分两种分治。

这是一篇在学术方面相对 trivial 的文章，主要是总结一些传统的非 CDQ 分治 NTT 的基本技巧。

求若干次数和一定的多项式之积

若有多项式 f_1,f_2,\dots,f_m 满足 \sum\limits_{i=1}^m \deg f_i = O(n)，那么我们可以用分治 NTT 在 O(n \log^2 n) 的复杂度内求出 \prod\limits_{i=1}^m f_i。
在实现方面，一个常见的误区是认为必须合并果子地执行分治。事实上并不是，直接在中点分治的复杂度也是正确的。

求若干次数和一定的有理分式之和

若有有理分式 \frac{p_1}{q_1},\frac{p_2}{q_2},\dots,\frac{p_m}{q_m} 满足 \sum\limits_{i=1}^m \deg p_i = O(n) 和 \sum\limits_{i=1}^m \deg q_i = O(n)，那么我们可以用分治 NTT 在 O(n \log^2 n) 的复杂度内求出 \sum\limits_{i=1}^n \frac{p_i}{q_i}。
分治时维护分子和分母并实时通分即可。

处理一些路径相关的树上问题

经典问题是统计所有长度的路径条数，其他形式也多半是不超过路径长度的若干信息通过直接拼接的卷积来合并。
那么我们可以用点分治 NTT 在 O(n \log^2 n) 的复杂度内求出答案。
实现上需要注意的细节是，合并时必须按照多项式度数从小到大执行合并。

结合矩阵

这个相对比较 trivial，大概就是利用矩阵乘法和 NTT 执行乘法，并用分治平衡复杂度。

求前缀积之和及相关衍生问题

能做的东西大概是对于多项式 f_1,f_2,\dots,f_m,g_1,g_2,\dots,g_m,a_1,a_2,\dots,a_m 满足 \sum\limits_{i=1}^m \deg f_i = O(n) 和 \sum\limits_{i=1}^m \deg g_i = O(n) 和 \sum\limits_{i=1}^m \deg a_i = O(n)，那么我们可以用分治 NTT 在 O(n \log^2 n) 的复杂度内求出

\sum\limits_{i=1}^m f_1 f_2 \cdots f_{i-1} a_i g_{i+1} g_{i+2} \cdots g_m

状物。
考虑维护区间的 f 积，g 积和答案即可。
换成矩阵也是一样的。

处理右复合

考虑多项式 F(z) 右复合 u，其中 n = \deg F，那么考察 u^0,u^1,\dots,u^n，这一族多项式若存在可以用矩阵描述的递推关系，即转化为以上问题。
在 u 包含二次根式时通常比较有用。

例：[数据删除] from Mivik
[数据删除]

[数据删除]
[数据删除]
听说这题被 O(n) 干爆了，懒得写了（

结合转置原理

在适当的时候考察对应问题的转置，若其能够使用分治 NTT 解决，那么转置就可以解决原问题。

处理右复合

考虑多项式 F(z) 右复合 u，其中 n = \deg F，那么考察

\sum\limits_{i=0}^n f_i u^i = \sum\limits_{i=0}^n i! f_i [t^i] \mathrm e^{tu}

那么考虑其转置就是

\sum\limits_{i=0}^n i! f_i [z^i] \mathrm e^{tu}

若 \mathrm e^{tu} 满足一个关于 z 的 ODE，即可以写出 [z^i] \mathrm e^{tu} 的转移矩阵，则可用分治 NTT 解决。

例：Feux Follets
对于给定的多项式 F(z)，考虑计算 F\left(\ln\frac1{1-z}-z\right)。

传送门

处理一些和深度相关的树上问题

基本形式是刚才的问题上树，前缀变成到根的链。
通常考虑首先确认一条链上如何处理，然后加上一个长链剖分。

例：(「2020-2021 集训队作业」Tree & Primes)^T
对于给定的树和序列 a,p，考虑计算

\sum\limits_u a_u \prod\limits_{i\in \mathrm{Path}(1,u)} (p_i x + 1 - p_i)

将先前提到的算法加上长链剖分即可。

处理一些和子树大小相关的树上问题

也就是优化树上背包。
即结合静态链分治（重链剖分 / dsu on tree / 全局平衡二叉树）。
不过这个 trick 通常需要结合矩阵，复杂度一般来说是 O(n \log^3 n) 或 O(n \log^2 n) 的。

例：Stranger Trees
给定一棵 n 个点的树，求出与这棵树恰有 k 条边重合的树的个数。

记 F(z,t) 是钦定若干条边重合的生成函数，z 计量点数，t 计量钦定的边数。
那么求出 [z^n] F(z,t) 后复合 t-1 即可（二项式反演）。
对于 [z^n] F(z,t)，我们考虑 Prufer 序列 / Matrix-Tree 定理 / 多元拉格朗日反演 导出的经典结论，可以通过组合意义或是对生成函数的求导转化为树上背包问题。
这样应用上述算法即可做到 O(n \log^3 n) 或 O(n \log^2 n)。