P13364 [GCJ 2011 Qualification] GoroSort

Goro 有 4 只手臂。Goro 非常强壮。你可别惹 Goro。Goro 需要对一个包含 $N$ 个不同整数的数组进行排序。算法不是 Goro 的强项，力量才是 Goro 的强项。Goro 的计划是用两只手的手指按住数组中的若干元素，然后用另外两只手狠狠地敲桌子。这样，未被固定的元素会飞到空中，被随机打乱后再落回原来的空位。 Goro 想要尽快将数组排序。如果 Goro 每次都聪明地选择要固定哪些元素，平均需要敲多少次桌子才能将给定的数组排序？Goro 用来固定数组的两只手有无限多的手指。 更具体地说，在每次敲桌子之前，Goro 可以选择数组中的任意子集元素将其固定在原位。每次可以根据之前敲桌子的结果选择不同的固定方式。每次敲桌子会将未固定的元素等概率地随机排列。每种排列出现的概率相同。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据包含两行。第一行为整数 $N$。第二行为数组初始顺序下的 $N$ 个元素。

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为在采用最佳固定策略时，期望的敲桌子次数。只要答案的绝对误差或相对误差不超过 $10^{-6}$ 即视为正确。

**样例解释** 在第 3 个测试用例中，一种可行的策略是先固定最左边的两个元素。元素 3 和 4 没有被固定。敲桌子后，它们有 $1/2$ 的概率变为正确顺序 $[3, 4]$，有 $1/2$ 的概率变为错误顺序 $[4, 3]$。因此，平均需要 2 次敲桌子才能将它们排好。之后，Goro 可以固定元素 3 和 4，再敲桌子直到 1 和 2 排好，平均也需要 2 次。总共期望敲桌子次数为 $2 + 2 = 4$。 **数据范围** - $1 \leq T \leq 100$； - 每组测试数据的第二行为 $N$ 个最小正整数的一个排列。 **小数据范围（10 分，测试点 1 - 可见）** - $1 \leq N \leq 10$； - 时间限制：~~30~~ 3 秒。 **大数据范围（20 分，测试点 2 - 隐藏）** - $1 \leq N \leq 1000$； - 时间限制：~~60~~ 6 秒。 由 ChatGPT 4.1 翻译