自动搬运

查看原文

来自洛谷，原作者为

	Dr_Gilbert 比赛审核事宜请在工单沟通，不要私信沟通。

搬运于2025-08-24 22:01:23，当前版本为作者最后更新于2022-05-16 23:15:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

发现题解第一篇的结论比较缺乏证明，看题解的时候一直没看懂，后来自己想了想才理解结论的正确性，在此对结论补充一下证明。

要求最后一个关键点的期望位置，不妨求排在所有关键点后的非关键点的期望个数。任意钦定一个非关键点，去掉序列中所有其它非关键点。$k$ 个关键点将原序列分为了 $k+1$ 段，这个非关键点和关键点的位置关系与非关键点个数无关。故对于任意一个非关键点，它排在所有关键点后面的概率为

$$P=\frac{1}{k+1}$$

由于有 $n-k$ 个非关键点，则排在所有关键点后的非关键点的个数期望

$$E=(n-k)P=\frac{n-k}{k+1}$$

故最后一个关键点的位置期望

$$E=n-\frac{n-k}{k+1}=\frac{kn+n-n+k}{k+1}=\frac{k(n+1)}{k+1} $$

则答案为

$$\frac{k}{k+1}(n+1)!$$