题目描述

你正在参加“盛大 Kickstart 幸运抽奖”活动，奖品非常精彩且令人惊叹（也有些不太好的奖品）！

在这个幸运抽奖中，有一个装有 $N$ 个物品的袋子。袋子中的第 $i$ 个物品的价值为 $V_i$。你将把手伸进袋子，随机抽取一个物品；袋子中的所有物品被抽中的概率相等。组织者希望让参赛者感到自己有一定的选择权，因此在你抽出一个物品后，你可以选择保留它，或者将其放回袋子并重新抽取（即“重抽”）。注意，放回的物品与袋子中其他物品被抽中的概率相同。你最多只能重抽 $K$ 次。如果你使用了 $K$ 次重抽，则必须保留第 $(K+1)$ 次抽到的物品。

如果你以最优策略进行游戏，以最大化最终持有的物品价值，那么该物品的期望价值是多少？

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 个测试用例。

每个测试用例由两行组成。第一行包含两个整数 $N$ 和 $K$：袋子中的物品数量，以及最多可以重抽的次数。第二行包含 $N$ 个整数 $V_i$，表示第 $i$ 个物品的价值。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是上述期望价值。如果答案与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则认为正确。

5
4 0
1 2 3 4
3 1
1 10 1
3 15
80000 80000 80000
1 1
10
5 3
16 11 7 4 1

Case #1: 2.500000
Case #2: 6.000000
Case #3: 80000.000000
Case #4: 10.000000
Case #5: 12.358400

提示

在样例 #1 中，你不能重抽，所以期望价值就是袋子中物品的平均值，即 $(1 + 2 + 3 + 4) / 4 = 2.5$。

在样例 #2 中，最佳策略是：如果抽到价值为 $10$ 的物品就保留，否则重抽。第一次或第二次抽到该物品的概率为 $1 - (2/3)^2 = 5/9$，因此期望价值为 $(5/9 \times 10) + (4/9 \times 1) = 6$。

在样例 #3 中，由于所有物品价值相同，重抽多少次都没有影响，因此期望价值为 $80000$。

注意，样例 #3 和 #5 不会出现在小数据集中。

限制条件

$1 \le T \le 100$。

$1 \le V_i \le 10^9$。

$1 \le N \le 2 \times 10^4$。

小数据集（测试集 1 – 可见）

$0 \le K \le 1$。

大数据集（测试集 2 – 隐藏）

$0 \le K \le 5 \times 10^4$。

翻译由 DeepSeek V4 Pro 完成