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

分治 FFT

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

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

考虑分治。将当前区间一分为二后,我们先递归求解,然后统计区间对区间的贡献,最后递归求解

假设我们已经完成了对区间的统计。对于,对的贡献可以表示为

等号左右的量不相关,这就是一个比较标准的卷积形式了。我们把上界推到(即令),则可以得到

,得到

,则得到

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

总的时间复杂度

LOJ575 不等关系

给定一个字符串,仅包含<>两种字符。

计算有多少长度为的排列满足的关系是。答案对取模。

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

把容斥系数放在 DP 的式子里即可。设表示排列的前个数的方案数除以的结果。答案即为

其中。特别地,我们定义

直接 DP,复杂度。我们稍微变换一下式子

。这样就可以分治 NTT 了。

代码