E
题意简述
给长为 \(n\) 序列，随机等概率交换两个不同位置 (\(i<j\)) 的值，要求 \(a_i > a_j\) 时才能交换。
\(n\le 200000\)
但是强制要求 \(a_i > a_j\) 即 \(a_i = 1, a_j = 0\) 交换，那么意味着可以直接设
\(f_i\) 表示前 \(m\) 个位置有 \(i\) 个 \(0\) 的期望交换次数。
（如果没有那个限制就有后效性）
转移就是说，可以把前 \(m\) 个位置的 \(1\) 和后面的 \(0\) 交换，或者是
后 \(n-m\) 个位置的 \(1\) 和后 \(n-m\) 个位置的 \(0\) 交换。
那么 \(f_i = 1 + \dfrac{(m-i)(m-i)}{n(n-1)/2}f_i + \dfrac{(n+i-2m)(m-i)/2}{n(n-1)/2} f_{i-1}\)
移项以后可以整理成好一些的形式。
时间复杂度 \(O(n)\)。
标签：dfrac,位置,交换,Codeforces,829,Div,Round From： https://www.cnblogs.com/Lates/p/16830331.html