题解：P12735 回报

dead_X · 2025-06-07 22:59:47 · 题解

好久没写题解了。

怎么判定一个排列合不合法呢？答案是找到最左边的 a 环和最右边的 b 环，然后看看是不是不交的。

那就可以想到做一个分界点，然后枚举左边的一个 a 环和右边的一个 b 环，和原问题需要一步点减边 Trick 的转化。

那么现在的问题是对于长度为 n，存在至少一个长度为 a 的环计数。至少一个肯定不如钦定一个好做，只需要一次容斥就可以完成这步转化。

然后就是交换循环顺序，变成枚举 a 环数量，枚举 b 环数量再枚举分界点，那么枚举分界点就可以用范德蒙德卷积优化掉。

最后会得出一个卷积的式子，FFT 即可，时间复杂度 O(n\log n)。

代码懒得给了。