题目描述

Panko 正在玩一个游戏，游戏中有 $N$ 张卡片排成一行。第 $i$ 张卡片上写有整数 $A_i$。

游戏进行 $N - 1$ 轮。在每一轮中，Panko 会选择一对相邻的卡片并将它们合并。假设两张卡片上写的整数分别为 $X$ 和 $Y$。合并时，Panko 会创建一张新卡片，上面写有 $X + Y$。然后他从行中移除原来的两张卡片，并将新卡片放在它们原来的位置上。最后，Panko 获得 $X + Y$ 分。在每一轮中，Panko 会从所有可用的相邻卡片对中均匀随机选择一对。

在所有 $N - 1$ 轮结束后，Panko 的总分是他每轮获得的分数的总和。求游戏结束时 Panko 总分的期望值。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$。第二行包含 $N$ 个整数，描述初始的卡片行。其中第 $i$ 个整数是 $A_i$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是游戏结束时的期望总分。

如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则认为正确。请参阅常见问题解答以了解其含义以及我们接受的实数格式。

2
3
2 1 10
5
19 3 78 2 31

Case #1: 20.000000
Case #2: 352.33333333

提示

在样例 #1 中，$N = 3$。初始卡片行为 $[2, 1, 10]$。在第一轮中，Panko 有 $2$ 种选择，他会随机选择其中一种。

• 如果 Panko 合并第一对 $(2, 1)$，则卡片行变为 $[3, 10]$，总分增加 $2 + 1 = 3$ 分。在第二轮中，只剩下一对 $(3, 10)$。如果他合并它们，卡片行变为 $[13]$，总分增加 $3 + 10 = 13$ 分。Panko 最终得分为 $3 + 13 = 16$ 分。
• 如果 Panko 合并第二对 $(1, 10)$，则卡片行变为 $[2, 11]$，总分增加 $1 + 10 = 11$ 分。在第二轮中，只剩下一对 $(2, 11)$。如果他合并它们，卡片行变为 $[13]$，总分增加 $2 + 11 = 13$ 分。Panko 最终得分为 $11 + 13 = 24$ 分。

因此，Panko 结束时得分的期望值为 $(16 + 24) / 2 = 20$。

在样例 #2 中，$N = 5$。初始卡片行为 $[19, 3, 78, 2, 31]$。此处无法列出所有可能性，我们仅演示一种可能的游戏过程：

• 在第一轮中，如果 Panko 合并对 $(78, 2)$，则卡片行变为 $[19, 3, 80, 31]$，得分增加 $78 + 2 = 80$。
• 在第二轮中，如果 Panko 合并对 $(80, 31)$，则卡片行变为 $[19, 3, 111]$，得分增加 $80 + 31 = 111$。
• 在第三轮中，如果 Panko 合并对 $(19, 3)$，则卡片行变为 $[22, 111]$，得分增加 $19 + 3 = 22$。
• 在第四轮中，如果 Panko 合并对 $(22, 111)$，则卡片行变为 $[133]$，得分增加 $22 + 111 = 133$。

在上述游戏过程结束时，Panko 的总分为 $80 + 111 + 22 + 133 = 346$。

限制条件

$1 \le T \le 100$。

对于所有 $i$，$1 \le A_i \le 10^9$。

测试集 1

$2 \le N \le 9$。

测试集 2

$2 \le N \le 100$。

测试集 3

$2 \le N \le 5000$。

翻译由 DeepSeek V4 Pro 完成