admin官方

我们记 fif_i 表示 val(p)=i\text{val}(p)=i 的排列个数，考虑如何计算 fif_i：

  • 对于 ∀1≤j<i\forall 1\le j<i，pj≥jp_j\ge j；
  • 对于 ii，pi<ip_i<i；
  • 对于 ∀i<j≤n\forall i<j\le n，没有限制。

我们枚举 pi=jp_i=j，容易得到：

fi=(n−i)!∑j=1i−1(n−i+2)i−1−j(n−i+1)j=(n−i)!(n−i+2)i−1(∑j=1i−1(n−i+1n−i+2)j)=(n−i+1)!((n−i+2)i−1−(n−i+1)i−1)\begin{aligned} f_i&=(n-i)!\sum\limits_{j=1}^{i-1} (n-i+2)^{i-1-j}(n-i+1)^j\\ &=(n-i)!(n-i+2)^{i-1}\left(\sum\limits_{j=1}^{i-1}\left(\frac{n-i+1}{n-i+2}\right)^j\right)\\ &=(n-i+1)!\left((n-i+2)^{i-1}-(n-i+1)^{i-1}\right) \end{aligned}

显然所有排列的 val(p)\text{val}(p) 之和为 ∑i=1n(i⋅fi)+n+1\sum\limits_{i=1}^{n} \left(i\cdot f_i\right)+n+1，将此结果除以 n!n! 即为期望。

时间复杂度 O(nlog⁡n)\mathcal O(n\log n)。