CF1726E Almost Perfect

Sol

首先不难注意到 \(p_i\) 和 \(p^{-1}_{i}\) 是距离恰好为 \(2\) 的点对。

然后不难想到图中每个连通块一定是 \(1,2,4\) 元环。

考虑只有 \(1,2\) 元环怎么做，考虑 DP，\(f_i\) 表示 \(i\) 个点的方案数，显然 \(f_{i}=f_{i-1}+(i-1)f_{i-2}\)。

然后枚举 \(4\) 元环的个数，假设选了 \(k\) 个四元环，那么就是选了 \(2k\) 对相邻的点，假设选的点对分别为 \((p_1,p_1+1),(p_2,p_2+1),\dots,(p_{2k},p_{2k}+1)\)，记 \(p_0=0,p_{2k+1}=n\)，令 \(d_i=p_i-p_{i-1}\)，那么 \(p\) 的方案数就等价于求出满足以下条件的 \(d\) 的数量：

1. \(d_1\ge 1\)
2. \(d_{2k+1}\ge 1\)
3. \(d_{i}\ge 2(2\le i \le 2k)\)

显然可以用插板法计算。

最后考虑四元环的方案数，等价 \(2k\) 个点组成有序数对的方案数，即 \(\dfrac{(2k)!}{k!}\)。

Code

Link。