题目描述

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}$ 以内，则认为正确。

2
3 6 2
1
2
5 2 1
5

Case #1: 4.7
Case #2: 9.0

提示

在样例 #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 完成