P16770 [GKS 2020 #F] Yeetzhee

Pommel 在家非常无聊，于是她发明了一个涉及 $N$ 个骰子的新游戏。每个骰子上写有从 $1$ 到 $M$ 的数字。当她掷一个骰子时，落在 $M$ 个可能值中每一个的概率均等。 Pommel 将所有骰子排成一行。她从左到右依次处理每个骰子。对于每个骰子，她掷出后可以选择保留掷出的数值并继续下一个骰子，或者重新掷该骰子。Pommel 在继续下一个骰子之前可以任意多次重掷当前骰子。 当 Pommel 处理完所有骰子后，游戏结束。为了判断她是否获胜，她将骰子分组。所有数值相同的骰子被分到同一组。因此，如果她最终有 $x$ 个不同的数值，那么就会有 $x$ 组。然后这些组按组内骰子数量非递减顺序排列。 例如： - 如果最终骰子结果为 $[2, 2, 3, 2, 2, 3]$，骰子会被分成 $2$ 组，排序后为：$[3, 3]$ 和 $[2, 2, 2, 2]$。 - 如果最终骰子结果为 $[1, 6, 7, 7]$，骰子会被分成 $3$ 组，排序后为：$[6]$、$[1]$ 和 $[7, 7]$（或者等价地 $[1]$、$[6]$ 和 $[7, 7]$）。 如果 Pommel 最终恰好有 $K$ 组，并且对于所有 $i$，第 $i$ 组恰好包含 $A_i$ 个骰子，则她获胜。 假设 Pommel 采取最优策略以最小化获胜所需的期望总掷骰次数，求该期望值。 保证对于任何有效的输入，Pommel 都有可能获胜。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $N$、$M$ 和 $K$。随后 $K$ 行描述她最终必须得到的各组。第 $i$ 行包含 $A_i$。

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

在样例 #1 中，Pommel 有 $N = 3$ 个骰子，每个骰子上的数字为 $1$ 到 $M = 6$。要获胜，她必须最终有 $K = 2$ 组。一组必须包含 $1$ 个骰子（$A_1 = 1$），另一组必须包含 $2$ 个骰子（$A_2 = 2$）。Pommel 的一种最优策略如下： - Pommel 掷第一个骰子 $1$ 次。 - Pommel 掷第二个骰子 $1$ 次。 - 如果第一个和第二个骰子的结果相同，Pommel 不断掷第三个骰子，直到它得到与前两个不同的数值。平均需要 $1.2$ 次掷骰。 - 如果第一个和第二个骰子的结果不同，Pommel 不断掷第三个骰子，直到它匹配第一个或第二个骰子的数值。平均需要 $3$ 次掷骰。 这种策略下，Pommel 平均需要 $4.7$（$1 + 1 + 1/6 \times 1.2 + 5/6 \times 3$）次掷骰。 在样例 #2 中，Pommel 有 $N = 5$ 个骰子，每个骰子上的数字为 $1$ 到 $M = 2$。要获胜，她必须最终有 $K = 1$ 组，且该组包含所有 $5$ 个骰子（$A_1 = N$）。对于骰子 $1$，Pommel 掷它 $1$ 次。然后，对于剩下的每个骰子，她不断掷直到它与骰子 $1$ 的数值相同。平均需要 $2$ 次掷骰。 这种策略下，Pommel 平均需要 $9$（$1 + 2 + 2 + 2 + 2$）次掷骰。 ### 限制条件 $1 \le T \le 100$。 $1 \le K \le M$。 对于所有 $i$，$1 \le A_i$。 $A_1 + A_2 + \dots + A_K = N$。 对于所有 $i$，$A_i \le A_{i+1}$。 **测试集 1** $2 \le N \le 6$。 $2 \le M \le 6$。 **测试集 2** $2 \le N \le 50$。 $2 \le M \le 50$。 翻译由 DeepSeek V4 Pro 完成