SP7566 IITD5 - Expected Cycle Sums

给定一个包含 $N$ 个不同整数组成的序列 $S$，其中 $S[i]$ 表示序列 $S$ 的第 $i$ 个元素。现在，Hardik 随机选择 $S$ 的一个排列，将其分解为若干个不相交的循环，并关注包含元素 $S[i]$ 的循环。他计算出这个循环中所有元素的总和。将这个和的期望值记为 $cycleSum[i]$。你的任务是找出所有 $cycleSum$ 中的最小值。 假设所有可能的排列都是等概率的。

第一行是一个整数 $T$，表示测试用例的数量。接下来是 $T$ 组测试数据的描述。每组测试数据的第一行是一个整数 $N$，表示序列 $S$ 的大小。第二行包含 $S$ 的 $N$ 个元素。

对于每个测试用例，输出结果，每行保留一位小数。

- $1 \le T \le 500$ - $1 \le N \le 5000$ - $S$ 中的所有元素都是范围在 $0$ 到 $10^5$ 之间的不同整数。 ## 样例解释 在第一个测试用例中，唯一的排列是 $(1)$，答案显然是 $1.0$。 在第二个测试用例中，可能的排列有 $(1)(2)$ 和 $(12)$，由于这两种情况出现的概率是相同的，计算得出 $cycleSum[1] = \frac{1}{2} \times 1 + \frac{1}{2} \times (1+2) = 2.0$，而 $cycleSum[2] = \frac{1}{2} \times 2 + \frac{1}{2} \times (1+2) = 2.5$。因此，较小的值是 $2.0$，答案为 $2.0$。 **本翻译由 AI 自动生成**