半在线卷积入门

本文原标题「分治 FFT/NTT 学习笔记」，不过这容易与分治 + NTT 混淆，因此在接触到半在线卷积的概念后果断更名。

半在线卷积 I

考虑计算序列$f_0, \ldots, f_n$，其中$f$由卷积得到：

$$f_i=\sum_{j=0}^{i-1}f_jg_{i-j-1} \qquad (i > 0)$$

$g_0, \ldots, g_n$是个已知序列，$f_0$值已知。

求逆

首先要说，上述问题可以直接通过多项式求逆解决。设两者的生成函数$F(x) = \sum _i f_i x^i, G(x) = \sum_i g_i x^i$。那么

$$FGx + f_0 = F$$

因此得到$F = \frac {f_0}{1-Gx}$。

多项式求逆的复杂度为$O(n\log n)$。

分治卷积

分治卷积，也称分治 FFT/NTT，指将贡献通过分治转化为离线卷积，通过多项式卷积的方式计算贡献。

我们定义记号$F[l, r]$表示多项式$\sum_{i = l} ^ r f_i x^i$，也就是$f$序列的区间$[l, r]$对应的生成函数。

另外我们定义$F \to G[l, r]$表示多项式$F$的每一项系数有对$G[l, r]$的对应项系数的贡献。简而言之，这描述的是对于任意$l\le i \le r$，令$g_i \gets g_i + f_i$。

这样我们就可以较为严谨地描述分治卷积的算法过程。定义$\text{Solve}(l, r)$表示$F[l, r]Gx \to F[l, r]$的操作。换言之$\text{Solve}(l, r)$计算区间$[l, r]$的半在线卷积的贡献。

考虑分治。那么对于区间中点$mid$：

1. 先递归地调用$\text{Solve}(l, mid)$来计算出$F[l, mid]$的全部系数。
2. 累加$F[l, mid]$对$F[mid+1, r]$的贡献。
3. 再调用$\text{Solve}(mid+1, r)$来计算$F[mid+1, r]$的全部系数。

第二步可以形式化地描述为操作$F[l, mid] Gx \to F[mid+1, r]$。

$O(n^2)$暴力执行这一操作复杂度过高。为了降低复杂度，我们首先考虑限定$G$的区间，因为$G$中并不是每个系数都能贡献到$[mid+1, r]$。简单计算一下可以发现该操作等价于$F[l, mid] G[0, r - l - 1]x \to F[mid+1, r]$。

区间范围计算过程

考虑$[l, mid]$和$[mid+1, r]$的区间端点。那么设$Gx$对应的区间是$[L, R]$。则有

$$\begin{cases} L \le mid + 1 - mid \le R\\ L\le r - l \le R \end{cases}$$

这样可以得到$L = 1, R = r-l$（一些小的边界情况就不考虑了）。

因此$G$对应的区间就是$[L-1, R-1]$， 也就是$[0, r-l-1]$。

由于$F[l, mid]$的系数已经通过第一步的递归计算得到，那么我们可以计算$\frac{F[l, mid]}{x^l}$与$G[0, r-l-1]$的多项式卷积来得到对$F[mid+1, r]$的贡献。

计算这个卷积的复杂度是$O((r-l)\log n)$。因此整个分治卷积的总时间复杂度为$O(n\log^2n)$。

半在线卷积 II¹

已知$f_0, g_0$，设$g_i = \bigoplus_{j = 0} ^ i f_j$。且

$$f_i = \sum_{j = 0} ^ {i-1} f_j g_{i-j-1} \qquad (i > 0)$$

求$f_0, \ldots, f_n$序列。

与上一个半在线卷积不同的是，$g$也是半在线的。这时我们可能会想到在分治卷积的过程中同时计算$f$和$g$。

假设我们已经计算好$F[l, mid]$和$G[l, mid]$，接下来考虑$[l, mid]$对$[mid+1, r]$的贡献。

错误策略

如果仍然采用$F[l, mid] G[0, r-l-1]x \to F[mid+1, r]$的分治卷积方式。

那么当$l=0$时就有$F[0, mid]G[0, r-1]x\to F[mid+1, r]$。

但是$G[mid+1, r-1]$还没有被正确地计算出来，因此这样计算是不对的。

这时我们需要利用分治卷积的一个性质：若令$mid = \lfloor\frac{l + r}{2}\rfloor$，那么在分治过程中若$l>0$，那么一定有$l \ge r-l+1$。

证明

考虑$[0, r]$递归到$\big[\lfloor\frac{r}{2}\rfloor+1, r\big]$的过程。则显然有$\lfloor\frac{r}{2}\rfloor + 1 \ge r - \lfloor\frac{r}{2}\rfloor$。

也就是说原策略在$l > 0$的情况是对的。所以我们得特殊处理$l = 0$的情况。我们将原策略修改一下：

当$l = 0$时：

• 执行$F[0, mid] G[0, mid] x \to F[mid+1, r]$。此时其他部分少掉的贡献是$F[0, mid] G[mid+1, r-1]x \to F[mid+1, r]$。

当$l > 0$时：

• 首先执行原策略$F[l, mid] G[0, r-l-1]x \to F[mid+1, r]$。
• 然后我们补上$l=0$时缺失的贡献，也就是$F[0, r-l-1] G[l, mid] x \to F[mid+1, r]$。

这样就可以使用分治卷积来计算了。总时间复杂度仍为$O(n\log^2n)$。

半在线卷积 III¹

对于多项式$F=\sum_{i} f_i x^i$和已知的多项式$G$，有

$$F = GF^2x + f_0$$

其中$f_0$已知。求$F \bmod {x^{n+1}}$。

仍然是考虑分治卷积。假设我们已经算出$F[l, mid]$，则$[l, mid]$对$[mid+1, r]$的贡献，有两种描述方式！

方法一

我们将贡献描述为$G[0, r-l-1]F^2[l, mid]x \to F[mid+1, r]$。

请注意$F^2[l, r]$和$(F[l, r])^2$代表的含义是不一样的。

如果要利用$F$暴力地计算$F^2[l, mid]$，那么可以执行$(F[0, mid])^2 \to F^2[l, mid]$。复杂度是$O(mid\log n)$，显然不能接受。

这时我们仍然考虑分治卷积的区间性质。

当$l = 0$时我们直接执行上述操作，复杂度是$O((r-l)\log n)$的。

否则$l > 0$，由于$l \ge r-l+1$，因此$2l \ge r+1$，换言之$(F[l, mid])^2$对$F^2[l, mid]$没有任何贡献。于是上述操作可以拆成

• $2F[0, l-1]F[l, mid] \to F^2[l, mid]$。
• $(F[0, l-1])^2 \to F^2[l, mid]$。

后者其实就是$[0, l-1]$对$[l, mid]$的贡献，是个半在线卷积的形式。因此我们设多项式$H=F^2$，然后同时分治卷积地计算$F$和$H$即可。

方法二

若$l = 0$，那么贡献仍描述为$G[0, r-l-1]F^2[l, mid]x \to F[mid+1, r]$。

若$l > 0$，那么我们将贡献描述为$2G[0, r-l-1]F[l, mid]F[0, l-1]x \to F[mid+1, r]$。

原因是$l\ge r-l+1$，因此$2l \ge r+1$，所以我们可以将$\sum_{i, j}f_i f_j[\max(i, j)\ge l]$拆分为$\sum_{i\ge l, j < l} f_j f_j + \sum_{i < l, j\ge l}f_i f_j$。写成生成函数的形式就得到了上式。

进一步约束范围可以得到$2G[0, r-l-1]F[l, mid]F[0, r - l-1]x \to F[mid+1, r]$。这样就可以$O((r-l)\log n)$计算贡献了。

总时间复杂度$O(n\log ^2 n)$。

方法二的应用参考 UOJ50 链式反应。

不等关系

给定一个字符串$s_1,s_2,\cdots,s_n$，仅包含<和>两种字符。

计算有多少长度为$n+1$的排列满足$p_i$和$p_{i+1}$的关系是$s_i$。答案对$998244353$取模。

考虑容斥，大于 = 无限制 - 小于。考虑我们将长度为$x$的排列分成$k$段，每一段的长度为$a_i$，段内的关系都是小于，段与段之间的关系是无限制。则这样的排列的方案数是

$$\binom{x}{a_1,a_2,\cdots,a_k}=\frac{x!}{\prod_{i=1}^ka_i!}$$

把容斥系数放在 DP 的式子里即可。设$f(i)$表示排列的前$i$个数的方案数除以$i!$的结果。答案即为$f(n+1)(n+1)!$。设$a_i = [s_i = '>']$。特别地，我们定义$s_0='>'$。

$$f(i)=\sum_{j=0}^{i-1}a_jf(j)\frac{1}{(i-j)!}(-1)^{C(i-1)-C(j)}\\ f(0)=0$$

其中$C(x)=\sum_{i=1}^xa_i$。

直接 DP，复杂度$O(n^2)$。我们稍微变换一下式子

$$f(i)=(-1)^{C(i-1)}\sum_{j=0}^{i-1}a_jf(j)\frac{1}{(i-j)!}(-1)^{C(j)}$$

设$F(j)=a_jf(j)(-1)^{C(j)},G(i-j)=\dfrac{1}{(i-j)!}$。这样就可以分治卷积了。

代码

¹. https://www.luogu.com.cn/blog/command-block/ban-zai-xian-juan-ji-xiao-ji ↩