上个世纪做过这题，然后今天比赛（abc295）出了道弱化没做出来，被 pty 喷了一遍后爬来写个题解/kk
首先这种期望/总和题都有个套路，就是通过另外一种角度来计算每个元素的贡献。对于此题，我们有：
\[ans=\sum_{i=1}^mi\cdot c(=i)=\sum_{i=1}^mc(\ge i)
\]
其中 \(c(P)\) 表示对于所有方案中的每个 \(a_i\)，满足条件 \(P\) 的数的数量。
于是考虑枚举 \(i\)，则我们需要维护 \(c(\ge i)\)，对一次操作，设这次操作选出的数为 \(v\)，我们有：
- \(v<i\)：\(c\) 不变。
- \(v\ge i\)：\(c\) 加一。
而在每次操作后，由于我们还要删除第 \(x\) 小的元素，所以还有：
- 操作完后，若 \(n+1-c<x\)，即 \(c>n+1-x\)，那么 \(c\) 减一。
可以发现，\(n+1-x\) 像一个界限，\(c\) 如果超过了它就会被压回去，所以我们可以先忽略删除第 \(x\) 小，在最后将 \(c\) 和 \(n+1-x\) 取 \(\min\) 即可。
考虑对于 \(k\) 次操作，其中有多少次操作将 \(c\) 加了一，设加了 \(p\) 次，那么方案数显然为 \((m-i+1)^p(i-1)^{k-p}\displaystyle{k\choose p}\)（没加一的方案数 乘上 加一的方案数 乘上 \(k\) 次操作中选出 \(p\) 次操作的方案数）
由于最后的 \(c\) 可以直接计算得到，故直接累加答案即可。
时间复杂度 \(O(m(n+k))\)