分治 FFT/NTT 学习笔记

由于 FFT 和 NTT 的应用是一样的，因此直接放在一起讲了。

分治 FFT

分治 FFT，指在分治的过程中利用 FFT 来统计贡献。一般而言，分治 FFT 适用于形如以下问题的求解：

$$f(i)=\sum_{j=0}^{i-1}f(j)g(i-j)$$

观察发现，右边是一个简单的卷积形式，但是它自己卷自己，所以不能直接使用 FFT 求解。

考虑分治。将当前区间$[l,r]$一分为二后，我们先递归求解$[l,mid]$，然后统计区间$[l,mid]$对区间$[mid+1,r]$的贡献，最后递归求解$[mid+1,r]$。

假设我们已经完成了对区间$[l,mid]$的统计。对于$i\in[mid+1,r]$，对$f(i)$的贡献可以表示为

$$c(i)=\sum_{j=l}^{mid}f(j)g(i-j)$$

等号左右的量不相关，这就是一个比较标准的卷积形式了。我们把上界推到$i-1$（即令$f(x)=0,x\in[mid+1,i-1]$），则可以得到

$$c(i)=\sum_{j=l}^{i-1}f(j)g(i-j)$$

设$a(i)=f(i+l),i\in[0,mid-l]$，$b(i)=g(i+1),i\in[0,r-l-1]$，得到

$$c(i)=\sum_{j=0}^{i-l-1}a(j)b(i-l-1-j)$$

令$z(i)=\sum_{j=0}^ia(j)b(i-j)$，则得到$c(i)=z(i-l-1)$。

这样就可以使用 FFT/NTT 求解$z$。

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

LOJ575 不等关系

给定一个字符串$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)!$。

$$f(i)=\sum_{j=0}^{i-1}[s_j='>']f(j)\frac{1}{(i-j)!}(-1)^{C(i-1)-C(j)}\\ f(0)=0$$

其中$C(x)=\sum_{i=1}^x[s_i='>']$。特别地，我们定义$s_0='>'$。

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

$$f(i)=(-1)^{C(i-1)}\sum_{j=0}^{i-1}[s_j='>']f(j)\frac{1}{(i-j)!}(-1)^{C(j)}$$

设$F(j)=[s_j='>']f(j)(-1)^{C(j)},G(i-j)=\dfrac{1}{(i-j)!}$。这样就可以分治 NTT 了。

代码