Codeforces 1726E - Almost Perfect

把排列的变换打出来找找规律，会发现对于合法的 $p$，置换后的 $p^{-1}$ 都很相似。

以下是截取的几个 $n = 10$ 时的合法情况。

[2,1,8,9,6,5,10,3,4,7] => [2,1,8,9,6,5,10,3,4,7]
[2,1,8,9,6,5,10,4,3,7] => [2,1,9,8,6,5,10,3,4,7]
[2,1,8,9,7,6,5,3,4,10] => [2,1,8,9,7,6,5,3,4,10]
[2,1,8,9,7,6,5,4,3,10] => [2,1,9,8,7,6,5,3,4,10]
[2,1,8,9,7,10,5,3,4,6] => [2,1,8,9,7,10,5,3,4,6]

于是我们把置换环画出来，会发现只有一元环、二元环和四元环，至于证明我是真不会。

先来看一、二元，就是这两种情况。

1. $p_i = i$
2. $p_i = j, p_j = i (i < j)$

这个东西是非常能预处理的。设 $f_i$ 代表排列有 $i$ 个元素时的方案数，则 $f_i = f_{i-1} + f_{i-2} \times (i - 1)$。

然后来处理四元环，四元环形如这个样子。

$$i \to j \to i+1 \to j+1 \to i$$

其中需要保证 $|i - j| > 1$。

我们考虑直接枚举四元环的个数 $t$，则我们需要在 $[1,n - 1]$ 之间选出 $2t$ 个数，剩下的那个 $1$ 是为了保证 $+1$ 以后不会超过 $n$ 的，方案数为 $\binom{n-2t}{2t}$。

再把这些数两两组合成二元组，不妨直接任意排列，计相邻两项是二元组，方案数为 $\frac{(2t)!}{t!}$。

最后再把一、二元环的答案加回来。

综上，做完了。

$$Ans = \binom{n-2t}{2t} \frac{(2t)!}{t!} f_{n - 4t}$$