上个世纪做过这题,然后今天比赛(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))\)
标签:方案,题解,Priority,ge,ARC139D,操作 From: https://www.cnblogs.com/bykem/p/17258502.html