qbxt DAY7 T2

qbxt DAY7 T2

考虑序列中的每一个点对于答案的贡献即可

那么也就只需要考虑(n = 2)的情况

当(n = 2)时，产生逆序对的情况一定是第二个数先被加入，也就是说在(2k)次移动中，只有最后一次选择了第二个数

此时的概率是

(egin{aligned} & sumlimits_kq^{2k-1}p (q=p-1) \& =p imes(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 ightarrow infty)时，(q^{n+2} ightarrow 0)

(S=frac{q}{1-q^2})

则原式(=frac{pq}{1-q^2})

那么最后只需要输出

(Large frac{pq n(n-1)/2}{1-q^2})