P16774 [GKS 2020 #G] Merge Cards

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}$ 以内，则认为正确。请参阅常见问题解答以了解其含义以及我们接受的实数格式。

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