P4562 [JXOI2018]游戏

· · 题解

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

要求最后一个关键点的期望位置，不妨求排在所有关键点后的非关键点的期望个数。任意钦定一个非关键点，去掉序列中所有其它非关键点。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)!