题解：P12735 回报

好久没写题解了。

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

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

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

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

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

代码懒得给了。