====== Contest Info ======

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

[[https://ac.nowcoder.com/acm/contest/5671|2020牛客暑期多校训练营（第六场）]]

====== Solutions ======

===== A. African Sort =====

**题目大意**：给你一个排列，每次选一个子集 $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}
$$

显然可以用前缀和维护。

===== B. Binary Vector =====

**题目大意**：求有多少 $n\times n$ 的模 $2$ 意义下的矩阵满秩。

**题解**：注意到，为了使第 $i$ 个行向量与前面的行向量线性无关，有 $2^{i-1}$ 种向量不能取。因此答案为 $f_{n}=\prod_{i=1}^{n}(2^{n}-2^{i-1})$，它等于 $2^{n}(2^{n}-1)f_{n-1}$，因而可以递推。

===== C. Combination of Physics and Maths =====

签到题。

===== E. Easy Construction =====

签到题。