1.P10547 的一个结论（虽然当时不会 dp。。。）
一个排列的最小交换代价是 \(\dfrac{\sum |i-p_i|}{2}\)。
注意到若设每个点的势能是 \(|i-p_i|\)，一次代价为 \(W\) 的操作的最多使得总势能减少 \(2W\)。因此有不等式：
\[Ans\ge \frac{\sum |i-p_i|}{2} \]猜想其可以取到下界。证明：
只需说明对于每个非恒等的排列有一个使总势能减少 \(2W\) 的操作即可，然后施加归纳法即可。设原排列为 \(p\)，逆排列为 \(r\)，则等价于存在：
\[\exists i\neq j,i\le r_j<r_i\le j \]取 \(i\) 为最小的 \(i\neq p_i\)，\(j\) 为 \([i,r_i]\) 中一个 \(k\) 使得 \(p_k\ge r_i\) 即可。这样的 \(i,j\) 总是存在的。
2.证明：\(\sigma (n)=o(n)\)。
取
\[n=\prod_{i\le m}p_{i} \]那么
\[\frac{\sigma(n)}{n}=\prod_i (1+\frac{1}{p_i})\ge \sum _i \frac{1}{p_i} \]是不收敛的。
标签：势能,排列,frac,闲话,sum,ge,prod From： https://www.cnblogs.com/british-union/p/18254908/a618