圆桌彩票

p位玩家围绕圆桌而坐，游戏开始时每人随机获得一张未刮开的彩票。 彩票刮开后会显示1到p的之间的一个整数，表示可以获得的金额，任意两张彩票上的数额都不相同。 玩家的游戏目标是最大化其彩票收益。 随机选择一人作为第一个玩家，并选择一个顺序（顺时针或逆时针），玩家依次决定其行动。 每位玩家可以选择刮开自己的彩票并展示数额给所有人，也可以选择一位持有已刮开彩票的玩家进行交易，然后带着所获得的（已刮开的）彩票离场，被交易的玩家拿到未刮开彩票后需要将其刮开并展示给所有人。 当所有彩票都刮开后游戏结束，所有玩家持其当前彩票离场。 设所有玩家都使用最优策略以最大化其彩票收益。记$E(p)$是为游戏结束时还在场上的人数的期望值，例如可以验证$E(111)\approx5.2912$。 记$S_1(N)=\sum_{p=1}^NE(p)$，并对大于1的k记$S_k(N)=\sum_{p=1}^NS_{k-1}(p)$。 求$S_{20}(10^{14})$，用科学计数法写出答案，尾数和指数间用小写字母e分隔，并保留10位有效数字，例如$S_3(100)$的结果按此规则应写作$5.983679014e5$。

本题难度:

解答

本题似乎就是所谓的Hyper hamonic number。 首先注意到$E(p)=1+1/2+\ldots+1/p$，直接代入计算可得 $$S_k(N)=\sum_{x=1}^N\frac{\binom{k+N-x}{k}}{x},$$ 用Wolfram Alpha可以化简得 $$S_k(N)=\binom{k+N}{k}\sum_{x=1}^N\frac{1}{k+x}\approx\binom{k+N}{k}\ln\frac{k+N}{k},$$ 此和式也可直接用Wolfram Alpha计算，最终结果是$1.200856722e263$。 本题无需编程。