P1138

【POJ Challenge】吉他英雄

【POJ Challenge】吉他英雄

1tthinking 非常喜欢玩游戏《Guitar Hero》。游戏中共有 NN 首歌曲，编号为 11 到 NN。

游戏会等概率随机生成一个排列 P=⟨P1,P2,…,PN⟩P=\langle P_1,P_2,\ldots,P_N\rangle。播放完第 ii 首歌曲后，游戏会继续播放第 PiP_i 首歌曲。因此，这 NN 首歌曲会按照排列 PP 被划分为若干个循环。

例如，当 N=3N=3 且 P=⟨2,1,3⟩P=\langle 2,1,3\rangle 时，歌曲会形成 {1,2}\{1,2\} 和 {3}\{3\} 两个循环。

每首歌曲都有一个积分值。1tthinking 最喜欢 Queen 的歌曲《Another One Bites The Dust》，并且每次游戏都会选择这首歌曲开始游玩。他知道，这首歌曲的积分值在所有歌曲的积分值中排名第二高。重复的积分值需要分别计数：将所有积分值按非降序排列为

W1≤W2≤⋯≤WN,W_1\le W_2\le\cdots\le W_N,

则这首歌曲的积分值为 WN−1W_{N-1}。

从这首歌曲开始，1tthinking 会依次游玩它所在循环中的所有歌曲，并获得这些歌曲的积分值之和。给定所有歌曲的积分值，请计算一次游戏中 1tthinking 所获积分之和的期望。

例如，有 33 首歌曲，积分值分别为 11、22、33，那么 1tthinking 总会选择积分值为 22 的歌曲。所有可能的排列共有 66 个：

⟨1,2,3⟩, ⟨1,3,2⟩, ⟨2,1,3⟩, ⟨2,3,1⟩, ⟨3,1,2⟩, ⟨3,2,1⟩.\langle 1,2,3\rangle,\ \langle 1,3,2\rangle,\ \langle 2,1,3\rangle,\ \langle 2,3,1\rangle,\ \langle 3,1,2\rangle,\ \langle 3,2,1\rangle.

在这些排列中，他所选择的歌曲所在的循环依次为 {2}\{2\}、{2,3}\{2,3\}、{1,2}\{1,2\}、{1,2,3}\{1,2,3\}、{1,2,3}\{1,2,3\}、{2}\{2\}，对应获得的积分分别为 22、55、33、66、66、22。因此期望积分为

2+5+3+6+6+26=4.\frac{2+5+3+6+6+2}{6}=4.

输入格式

第一行包含一个整数 TT，表示数据组数。

对于每组数据：

  • 第一行包含一个整数 NN，表示歌曲数量；
  • 第二行包含 NN 个整数 V1,V2,…,VNV_1,V_2,\ldots,V_N，其中 ViV_i 表示第 ii 首歌曲的积分值。

输出格式

对于每组数据，输出一个浮点数，表示所获积分之和的期望。

结果精确到 10−610^{-6}，并固定输出小数点后 66 位。

样例输入

1
3
1 2 3

样例输出

4.000000

数据范围

  • 2≤N≤502\le N\le 50；
  • 0≤Vi<2310\le V_i<2^{31}。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

1
3
1 2 3

输出

4.000000