P6944 [ICPC 2018 WF] Gem Island

宝石岛是位于太平洋中部的一个小岛。直到最近，它还被认为是地球上最贫穷但也是最和平的地方之一。如今，它既不贫穷也不和平。发生了什么？ 不久前的一个晴朗的早晨，宝石岛的所有居民都醒来时发现了一个惊喜。那天早上，他们每个人手中突然多了一颗闪闪发光的宝石。这些宝石在一夜之间神奇地出现了。这引起了极大的欢呼——每个人突然变得富有，他们终于可以买到他们梦寐以求的一切，他们岛的名字现在也更有意义了。 第二天早上，其中一位居民醒来时又发现了一个惊喜——她的宝石神奇地分裂成了两颗！接下来的每个晚上，岛上的一颗宝石（显然是从岛上的所有宝石中均匀随机选择的）都会分裂成两颗。 过了一段时间，宝石岛的居民拥有的宝石数量差异很大。有些人有很多，而许多人只有很少。为什么有些居民拥有的宝石比其他人多？他们是作弊了吗？他们只是幸运吗？还是有其他原因？ 岛上的长老们请求你的帮助。他们希望你能确定宝石分布的不均衡是否可以用纯粹的偶然性来解释。如果是这样的话，这将大大减少岛上的紧张局势。 岛上有 $n$ 位居民。你需要确定经过 $d$ 个夜晚宝石分裂后的宝石分布。特别地，你感兴趣的是拥有最多宝石的 $r$ 个人所持有的宝石总数的期望值。更正式地说，假设经过 $d$ 个夜晚后，$n$ 位居民持有的宝石数量按非递增顺序排列为 $a_{1} \ge a_{2} \ge \ldots \ge a_{n}$。那么 $a_{1} + \cdots + a_{r}$ 的期望值是多少？

输入由一行组成，包含三个整数 $n, d$ 和 $r (1 \le n, d \le 500, 1 \le r \le n)$，如题目描述所述。

输出前 $r$ 位居民在 $d$ 个夜晚后持有的宝石数量的期望值，绝对误差或相对误差最多为 $10^{-6}$。

时间限制：3 秒，内存限制：1024 MB。 题面翻译由 ChatGPT-4o 提供。