考虑序列中的每一个点对于答案的贡献即可
那么也就只需要考虑\(n = 2\)的情况
当\(n = 2\)时，产生逆序对的情况一定是第二个数先被加入，也就是说在\(2k\)次移动中，只有最后一次选择了第二个数
此时的概率是
\(\begin{aligned} & \sum\limits_kq^{2k-1}p\ (q=p-1) \\& =p\times(q^1+q^3+q^5+...) \end{aligned}\)
考虑对数列\(q^1+q^3+q^5+...+q^n\)求和
令\(S=q^1+q^3+q^5+...+q^n\)
\(S‘=q^2S=q^3+q^5+...+q^n+q^{n+2}\)
\(S‘-S=(q^2-1)S=q^{n+2}-q\)
\(S=\frac{q^{n+2}-q}{(q^2-1)}\)
当\(n\rightarrow \infty\)时，\(q^{n+2}\rightarrow 0\)
\(S=\frac{q}{1-q^2}\)
则原式\(=\frac{pq}{1-q^2}\)
那么最后只需要输出
\(\Large \frac{pq\ n(n-1)/2}{1-q^2}\)
原文：https://www.cnblogs.com/lcezych/p/13858817.html