CF715E 题解

· · 题解

最小交换次数等于 n - \text{环数}。所以题目要我们统计把 p, q 补全成排列，连边 p_i \to q_i，环数 = i 的方案数。

考虑把边根据 p_i, q_i 的是否已知状态分成四类：

  1. p \to q
  2. p \to 0
  3. 0 \to q
  4. 0 \to 0

注意若存在 p \to 0, 0 \to q 且 p = q，我们把它们合并成一个 4 类边。

对于 1 类边直接把它缩成一个点，记录一下是否形成环即可。

对于剩下的边，设 2 类边数量为 n_1，3 类边数量为 n_2，4 类边数量为 n_3。

对于 2 类边，我们考虑钦定一些边形成环，剩下的边接到 4 类边去，因为 0 \to 0 和 p \to 0 合并还是一条 0 \to 0。

设 f_i 为 2 类边形成 i 个环的方案数。枚举钦定了 j 条边形成环，有：

f_i = \sum\limits_{j = i}^{n_1} \binom{n_1}{j} \begin{bmatrix} j \\ i \end{bmatrix} (n1 - j + n3 - 1)^{\underline{n1 - j}}

最后乘的下降幂意义是，一条边 p_1 \to 0 可以和之后的还没处理的边 p_2 \to 0 合并变成 p_1 \to 0，也可以直接和一条 0 \to 0 边合并。

需要特判 n_3 = 0，此时 f_i = \begin{bmatrix} n_1 \\ i \end{bmatrix}。

再设 g_i 为 3 类边形成 i 个环的方案数。计算方法和上面一样，把 n_1 改成 n_2 即可。

最后设 h_i 为 4 类边形成 i 个环的方案数，有：

h_i = \begin{bmatrix} n_3 \\ i \end{bmatrix} n_3!

最后乘 n_3! 是因为我们填排列的时候可以任意排列这些边的顺序。

把 f, g, h 做加法卷积即可。

时间复杂度 O(n^2)。

code