分治 NTT 学习笔记

默认 $f_0=0$。

Part 1 自己卷别人

$f_n=\sum\limits_{i=0}^{n-1}f_{i}g_{n-1-i}$，$g$ 已知

考虑分治计算 $f_{[l,r]}$。

计算 $f_{[l,r]}$ 时，设 $mid=\lfloor\frac{l+r}{2}\rfloor$，先分治计算 $f_{[l,mid]}$，再将 $f_{[l,mid]}$ 对 $f_{[mid+1,r]}$ 的贡献加上。即计算出 $f_{[l,mid]}\times g_{[0,r-l]}$，并将结果按位加到 $f_{[mid+1,r]}$ 上。

若 $l=r$ 则直接返回。

例题：洛谷板题。

Part 2 自己卷自己

$f_n=\sum\limits_{i=0}^{n-1}f_if_{n-1-i}$

此时有一个 bug：计算 $f_{[l,r]}$ 时 $f_{[0,r-l]}$ 不一定已经知道。

但是注意到计算完 $f_{[l,mid]}$ 后 $f_{[0,mid]}$ 一定都知道，所以当且仅当 $l=1$ 时才会出现这个 bug。

那么依旧是分治计算出 $[l,mid]$ 后考虑计算 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。若 $l=1$，则此时只知道 $[1,mid]$，那么不妨把 $[0,r-l]$ 拆成 $[0,mid]$ 和 $[mid+1,r-l]$，先计算 $[1,mid]\times [0,mid]$，$[1,mid]\times [mid+1,r-l]$ 在 $[mid+1,r-l]$ 的某些信息明确后再计算。

具体的，分治计算 $[l,r]$ 时若 $l=r$ 则返回，否则先分治计算 $[l,mid]$，接下来分讨：

• 若 $l=1$，则计算 $[1,mid]\times [0,mid]$，贡献到 $[mid+1,r]$；

• 否则先计算 $[l,mid]\times [0,r-l]$，贡献到 $[mid+1,r]$，再计算 $[0,r-l]\times [l,mid]$，同样贡献到 $[mid+1,r]$；

  注意应用时可能会带一些系数，所以可能不满足交换律；

例题：【2025NOI模拟赛01】青蛙