题解 P6059 【[加油武汉]居家隔离】

很水的一题…但是感觉既然是这场比赛的A，那可能会比较需要一篇general一点的解释。 这题自己本来想枚举最后选的哪个数来做，但是发现根本不科学，自闭了半天。就是考虑钦定了一个数，如果不是最后一个取他，那么前 $k$ 个一定都放比他小的数，同时可以在他的位置和 $k$ 个之间也放一些比他小的数，但是这些方案对于不同的前 $k$ 个元素的最大值，方案是不同的，所以复杂度很假也很麻烦。 发现似乎直接枚举前 $k$ 个元素的最大值比较容易做。分成两类来讨论，第一类情况是成功取到了某个 $x$，另一类情况是不得不取最后一个，发现当且仅当集合里的最大值在前 $k$ 个才会发生。 1、第一种情况。对于每个最大值 $x$，取到他的概率是 $\frac{\binom{x-1}{k-1}}{\binom{n}{k}}$，在取到最大值为 $x$ 的情况下，期望就再乘上一个 $\frac{\mathrm{S-S_{p_x}}}{n-p_x}$。其中 $\rm S$ 表示集合元素的总和，$\rm S_x$ 表前 $x$ 小的元素的和，$p_x$ 表示 $x$ 是第几小的。不难发现这样是对的。 2、第二种情况。不难发现概率是 $\frac{\binom{n-1}{k-1}}{\binom{n}{k}}=\frac{k}{n}$ 。那么期望的话，发现这种情况下最后一个数是谁情况相同，概率均等。所以乘上一个 $\frac{\mathrm{S}-x_{\max}}{n-1}$ 就完了。 这个故事告诉我们「组合计数全靠编，编错就会傻半天」。 代码就不展示了，整个过程还是很显然的。