本文最后更新于：星期六, 八月 8日 2020, 5:48 下午
BunnyOJ 10001 「原创」期望逆序对
Source
http://139.224.115.97:5283/problem/10001
题目描述
逆序对，指在数列{$a$}中，存在$i< j(1\leq i,j\leq n)$，且$a_i>a_j$，我们就将$[a_i,a_j]$称为一对逆序对。
给定一个正整数$n$，请你计算对于任意一个由$1,2,3,\cdots,n$组成的排列，其期望逆序对个数是多少。
如当$n=3$时，其排列和逆序对个数如下：
| 全排列 | 逆序对个数 |
|---|---|
| $1,2,3$ | $0$ |
| $1,3,2$ | $1$，即为$[3,2]$ |
| $2,1,3$ | $1$，即为$[2,1]$ |
| $2,3,1$ | $2$，即为$[2,3],[3,1]$ |
| $3,1,2$ | $2$，即为$[3,1],[3,2]$ |
| $3,2,1$ | $3$，即为$[3,2],[3,1],[2,1]$ |
则其期望逆序对个数$E=\dfrac{0+1+1+2+2+3}{3!}=\dfrac{9}{6}=\dfrac{3}{2}$
最终结果需要输出两个整数$a,b$，表示期望逆序对个数为$\dfrac ab$，且$\dfrac ab$为最简分数，即$gcd(a,b)=1$。特殊地，如果结果为$0$，则输出0 1。如果结果为整数，则$b=1$。
输入格式
只有一行一个正整数$n$。
输出格式
只有一行，输出两个输出两个整数$a,b$，表示期望逆序对个数为$\dfrac ab$。对于$a,b$的要求详见题目描述。
样例输入1
1
样例输出1
0 1
样例输入2
3
样例输出2
3 2
数据范围
对于$30\%$的数据，$1\leq n\leq 8$。
对于$60\%$的数据，$1\leq n\leq 10^7$。
对于$90\%$的数据，$1\leq n\leq 10^{16}$。
对于$100%$的数据，$1\leq n\leq 10^{1000}$。
题解
解法1
设数列${a_n}$表示对于$n$的全排列，逆序对的总数。
考虑向$n-1$的全排列中插入$n$会使逆序对总数发生的变化，即：
1.由于对$n-1$的每个排列都有$n$个空隙可以插入$n$，即逆序对总数为$n\cdot a_{n-1}$。
例如，在$1,2,3$中插入$4$，则会变为$4,1,2,3$、$1,4,2,3$、$1,2,4,3$、$1,2,3,4$共$4$种可能的排列，而$3$的排列中逆序对的相对位置不变。
2.考虑插入$n$，$n$这个数产生的影响。由以上例子可以看出对于$n-1$的每个排列，插入$n$会使逆序对总数增加$(n-1)+(n-2)+(n-3)+\cdots+2+1=\dfrac{(n-1+1)(n-1)}{2}=\dfrac{n(n-1)}{2}$。因为$n-1$共有$(n-1)!$个排列，故再乘上$(n-1)!$。
综上，
则逆序对期望数
当$n=1$时，$a_1=0, E_1=0$。
则$E_n=\dfrac{n(n-1)}{4}$。
对于$100\%$的数据，加个高精度即可。
解法2
此为妙解。
当$n=1$时没有逆序对，答案为$0$。
考虑对于$n(n>1)$的全排列，必定能将所有排列两两配对，使得这两个排列互相对称，即其中一个排列完全颠倒就是另外一个排列。例如$2,3,1$与$1,3,2$。
观察两两配对的排列，因为两个排列对称，故其中一个排列的逆序对总数就是另外一个的正序对总数，例如$2,3,1$的逆序对是$[2,1],[3,1]$，而$1,3,2$的正序对是$[1,3],[2,3]$。所以两个排列的逆序对总数就是其中一个排列的逆序对总数与正序对总数之和，而一个含$n$个元素且没有重复元素的序列中逆序对+正序对总数就是该序列的总对数，即$\dfrac{n(n-1)}{2}$。
又因为两个配对的序列逆序对总数是$\dfrac{n(n-1)}{2}$，故期望数量为$E=\dfrac{n(n-1)}{4}$，故总的期望数量也为此。
