秩序感知题解

有两种思路可以解决这个题目。
思路1：
先解决一个问题，如何用最少的步数将一个已知排列排序。
不妨将排列看做图，比如n=3，排列a是a[1]=2,a[2]=3,a[3]=1,i向a[i]连边，显然可以连出一个n个点，n条边，每个点度数都为2的，可以有自环，且只有环的图。
首先对于自环，这些位置不需要和其他位置交换，因为它们已经在自己的位置上了。
然后对于其他环，要使步数最少，交换只会发生在环内，一个长度为k的环，需要k-1次交换才能变得有序，这里手玩几个小环应该就能得到结论。
所以交换次数=n-环个数
然后我们再来考虑之前的问题，如何求期望。
期望交换次数=n-期望环个数
所以不妨来求环的个数！设f[i]表示i的排列形成环的个数的期望。
考虑加入i+1，如果i+1在第i+1个位置，它会自成一环，环的数量会+1，否则环的数量不会增加，依旧是f[i]，转移也就非常显然了。

思路2：
我们想直接求期望交换步数。
设f[i]表示i的排列的期望交换步数，如何从f[i-1]转移到f[i]？依旧考虑i的位置：
1、如果i就在第i个位置，那么对期望步数不会产生影响；
2、如果i不在第i位，那么i的可能位置有i-1个，且其他i-1个数又有(i-1)!种可能的排列方式，这里有(i-1)*(i-1)!种方案的贡献为1，且其他i-1个数又要重新排序，因此贡献还要加上(i-1)个f[i-1]

以上两个DP的复杂度都是O(n)的，预处理阶乘逆元就可以把总复杂度变成线性。

线性处理阶乘逆元，emmm这里讲个比较简单的方法，复杂度数O(n+logn)的：
(n-1)!=n!/n
根据这个，知道n!的逆元，可以在O(n)时间逆推所有n!的逆元，只需要用先用快速幂求出n!的逆元即可。