date: 2020-07-27 12:00~17:00

2020牛客暑期多校训练营（第六场）

题目大意：给你一个排列，每次选一个子集 $S$，花费 $|S|$ 的代价将 $S$ 位置的所有元素随机打乱。问排好序的期望代价。

题解：题解（不甚严谨地）证明了：最优策略为对排列的每个环分别操作，每个环全部打乱。这个结论我们比赛时也猜到了，具体证明请看题解。

设 $f(n)$ 表示将一个长为 $n$ 的环排好序时的期望代价，$g(n)$ 表示将一个长为 $n$ 的随机排列排好序的期望代价。

$$ \begin{aligned} f(n)&=g(n)+n(n>1)\\ g(n)&=\frac{1}{n!}\sum_{i=1}^{n}{n-1\choose i-1}(i-1)!(n-i)!(f(i)+g(n-i))\\ g(n)&=\frac{1}{n}\sum_{i=1}^{n}(f(i)+g(n-i))\\ \end{aligned} $$

显然可以用前缀和维护。