summarization
有一个长为 \(n\) 的排列 \(p\), 现有甲乙两人轮流执行操作，甲是先手：
- 甲每次可以交换 \(p\) 中相邻的两个数 \(p_i,p_{i+1}\)
- 乙每次等概率执行下面两种操作的一种：
- 选择一对 \(p_i,p_{i+1}\)，且 \(p_i\le p_{i+1}\)，将其交换
- 选择一对 \(p_i,p_{i+1}\)，且 \(p_i\ge p_{i+1}\)，将其交换
甲希望操作数尽可能小，求使排列升序的期望操作数。
solution
甲每次可以使序列中的逆序对减 1，乙每次有 \(\frac12\) 的概率使逆序对减 1，\(\frac12\) 的概率使逆序对加 1。
根据期望的可加性，当甲乙都操作过一遍时，有 \(\frac12\) 的概率使逆序对减 2，\(\frac12\) 的概率逆序对不变。
所以，每操作两遍，逆序对期望减少 1，所以期望操作数就是逆序对数乘 2。
但是，要注意一下细节，如果逆序对数是奇数的话，那么最后一次甲操作完后序列已经升序，所以操作数要减 1。
code
就算个逆序对，不贴了。