题解：CF840A Leha and Function

· · 题解

本题在得到 F(n,k)=\frac{n+1}{k+1} 的结论后，贪心的部分是简单的（感觉本题很多赛时通过的选手其实没推出来具体式子也能猜出正确的贪心、通过此题），所以本题解主要说明 F(n,k) 的推导，共会给出两种不同的推导。

方法1：推式子

官方题解也提到有一种基于曲棍球等式（中文也称作朱世杰恒等式）的推导，但没有详细给出，这里详细说明一下。

按定义，F(n,k)=\sum_{i=1}^niP(x=i)，进而 F(n,k)=\sum_{i=1}^nP(x\ge i)。这是一步常见的转化，道理是考虑 P(x\ge 1)=P(x=1)+P(x=2)+\ldots +P(x=n),P(x\ge 2)=P(x=2)+\ldots +P(x=n),\ldots，因此会将 P(x=1) 计算 1 次、P(x=2) 计算 2 次、依此类推，因此等式两边相等。

接下来代入 P(x\ge i)=\frac{C_{n+1-i}^k}{C_n^k} 得到：

而曲棍球等式指出 $C_k^k+C_{k+1}^k+\ldots+C_n^k=C_{n+1}^{k+1}$,因此 $F(n,k)=\frac{1}{C_n^k}{C_{n+1}^{k+1}}=\frac{n+1}{k+1}$，得证。 附曲棍球等式的组合意义：考虑在一行 $n+1$ 个球里选择 $k+1$ 个球的方案是 $C_{n+1}^{k+1}$，又因为我们枚举假设选的最靠右的球是位置 $x+1$ 的球、则还需要在区间 $[1,x]$ 中再选择 $k$ 个球，因此该方案数也可以写作 $\sum_{k\leq x\leq n}C_x^k$，由此曲棍球等式得证。 ### 方法2：神秘的同分布 题解里给了这种证明，但我觉得太神秘了，求教了随机 CF grandmaster 才理解（并被他喷了一遍）。 首先假设最终取的数从小到大依次是 $a_1,a_2,\ldots,a_k$，并定义 $a_0=0,a_{k+1}=n+1$，然后定义 $d_i=a_i-a_{i-1}$，则 $d_1+d_2+\ldots+d_{k+1}=n+1$。 我们发现，给出一个 $d_1,\ldots,d_{k+1}$ 的方案，可以不重不漏的还原出一个 $a_1,\ldots,a_k$ 的方案，即两数组之间的方案是一一映射。 又因为对于 $d$ 数组而言，唯二的约束就是$d_1+d_2+\ldots+d_{k+1}=n+1$ 和 $d_i\ge 1$，因此 $d_1,\ldots,d_{k+1}$ 的地位完全相等、是同分布的，从而：$(k+1)\mathbb{E}(d_1)=n+1\rarr \mathbb{E}(d_1)=\frac{n+1}{k+1}$，而这就是 $n$ 个数字里最小的数字、也就是我们要的 $F(n,k)$。 回过头来看，为什么最开始我们唐突定义了$a_0=0,a_{k+1}=n+1$，而不是比如 $1$ 和 $n$？这是因为，在上面推导里，要求 $d_i$ 地位相当才成立，而例如定义 $a_0=1$ 会使得 $d_1$ 可以取 $0$，这与其它 $d_i\ge 1$ 就地位不相当了。