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} $$

显然可以用前缀和维护。

题目大意：求有多少 $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}$，因而可以递推。

签到题。

签到题。