水讨论区水到这么一道题P13364
一道得出结论并不困难的 Ad-hoc，不过证明还挺困难的
题意：给定一个排列，每次可以选择任意一个子集随机重排，求最优方案下，将排列变为有序的期望操作次数。
充分发扬人类智慧，每次选择重排所有 \(a_i \ne i\) 的位置，期望操作次数为初始排列中 \(a_i \ne i\) 的数的个数 \(cnt\)。
证明：
设重排元素个数为 \(n\)，则随机排列一共有 \(n!\) 个，对于某一位置的元素，它正好落在自己位置上的概率为 \(p = \frac{(n-1)!}{n!}\) 。因为共有 \(n\) 个元素，所以恰好有1个元素落在自己位置上的概率为 \(p \cdot n\)，即 \(1\)。由此得出在重排元素都不在自己位置上的情况下，每次随机重排都能使期望 \(1\) 个元素归位。使 \(cnt\) 个元素归位即需要 \(cnt\) 次。
但如何证明这是最优操作方案？
以下证明来自于此。
设该排列为 \(A\)，\(n(A)\) 为当前未归位的元素个数，\(x(A)\) 为最优方案下的期望操作次数。因为上面我们已经构造出了一种操作方式通过 \(n(A)\) 步归位了所有元素，所以可知 \(x(A) \le n(A)\)。下证明 \(n(A) \le x(A)\)。
引理：设 \(K\) 为非负整数，则对于任意非负整数 \(k \le K\), \(x(A)=k\) 等价于 \(n(A)=k\)。
我们通过数学归纳法证明这一点。
首先 \(K=0\) 的情况显而易见，为排列已经有序的情况，显然 \(x(A)=n(A)=0\)。
现在假设我们已经证明了该引理在 \(K\) 时成立，下证明它在 \(K+1\) 时也成立。
选择 \(A\) 使得 \(x(A)\) 为满足 \(x(A) > K\) 的 最小可能值（即，它是最优策略下期望敲桌子次数大于 \(K\) 的那些状态中期望最小的一个）。
设 \(T\) 为以下两种元素数量之和：
-
\(A_i \ne i\)
-
选择一些元素进行随机重排后，元素位置发生了变化。
根据 \(T\) 的定义，可知 \(T \ge n(A)\)。
因为 \(x(A) \ge K+1\)，\(n(A) \ge x(A)\)，可知 \(n(A) \ge K+1\)。
因此 \(T \ge n(A) \ge K+1\)。
定义 \(p_i\) 为 一次随机重排后 恰好有 \(i\) 个元素不在其位置上的概率；
对于每种 剩余 \(i\) 个未归位的情况，新期望为 \(f_i = x(A')\)。（即从新状态 \(A'\) 再继续最优策略所需期望操作次数）
如果 \(i \le K\)，根据归纳假设，有 \(f_i = i\)。\((1)\)
如果 \(i > K\)，则 根据 \(A\) 的构造，有 \(f_i \ge x(A)\)。\((2)\)
从状态 \(A\) 出发，操作一次后进入状态 \(A'\)，再按照最优策略操作，我们可以列出方程：
\(x(A) = 1 + \sum\limits_{i=0}^{T} p_i \cdot f_i\)
代入 \((1) (2)\)，整理得到：
\(x(A) \ge 1 + \sum\limits_{i=0}^{T} p_i \cdot i + \sum\limits_{i=K+1}^{T} p_i (x(A) - T)\)
根据 期望的线性性，我们有 \(\sum\limits_{i=0}^{T} p_i \cdot i \ge T-1\)。
最终整理得到：
\((x(A) - T) \cdot (1 - \sum\limits_{i=K+1}^{T} p_i) \ge 0\)。
因为第二项很明显大于 \(0\)，所以得到 \(x(A) - T \ge 0\)，即 \(x(A) \ge T\)。
因为 \(T \ge n(A)\)，所以 \(x(A) \ge n(A)\)。
结合前文所证 \(n(A) \ge x(A)\)，得到 \(n(A) = x(A)\)。
得证。
所以这题的答案就是 \(cnt\) 啊哈，写代码 \(10\) 行的事...
证明确实不容易，我自己是绝对证不来的 T^T