题面链接

Problem

给定一个长度为 $n$ 的排列，可以任意交换两个位置，求使得排列升序的最小操作数和方案数

Solution

套路：将每个数当前位置和目标位置连边，构成一个有多个环的图

观察图的构造，每个点出度入度都是1，所以所有环没有相交

于是得出目标情况就是 $n$ 个自环，并且在最优状态下，一定是将每个环分别变成自环。

定理：将一个长度 $n$ 的环变成自环，最少用 $n-1$ 操作

因为交换两个点会使得环大小总量减 1

答案1：最小操作数

根据定理，消去一个 $n$ 个点的环比 $n$ 个点少一次计算

所以设这个图有 $k$ 个非自环，答案为 $n-k$

我们设这个图有 $k$ 个环

根据乘法原理：方案数是每个环的方案数的积

下面我们将 “将一个环的点全部变成自环” 简称为 “将环变成自环”

我们设 $f_n$ 表示将一个长度 $n$ 的环变成自环的方案数

求 $f_n$ 时，应当已经求出 $f_{1...n-1}$

考虑枚举断点，将 $n$ 分成 $x,y$ 两部分，使$x+y = n$

根据加法原理：$f_n$ 由若干个 $f_x,f_y$ 运算后相加

设 $T(x,y)$ 表示将一个长度为 $i$ 的环交换一次变成 $x,y$ 两个环的方案数

当 $x=y$ 时，$T(x,y)=i/2$ , 其余情况为 $i$ (每个点两个选择，一半重复。$x=y$ 时操作对称，所以再除2)

两个环合并的操作由一个多重集组成，含有两个元素，数量分别为$x-1$和$y-1$。

所以得到$f_n$的计算式

$f_n = \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} T(i,n-i) \times f_i \times f_{n-i} \times \frac{(i-2)!}{(i-1)!(n-i-1)!}$

设 $k$ 个环的长度分别为 $l_1,l_2...,l_k$ , 则答案为

$f_{l_1} \times f_{l_2} \times .... \times f_{l_k} \times \frac{(n-k)!}{(l_1-1)!(l_2-1)!...(l_k-1)!}$

计算 $f_n$ 的复杂度为$O(n)$，总复杂度为 $O(n^2)$

优化

把 $f_n$ 的式子化简(或者oeis.org)，发现 $f_n=n^{n-2}$，于是复杂度优化成 $O(nlogn)$

启发

处理排列交换问题一般转换成图的问题