CF1773A Amazing Trick（随机/Hall定理）

· · 题解

题目等价于（不是翻译）给定一个排列 \{a\}，让你构造一个排列 \{p\} 使得 \{p\} 错排于 \{a\} 和顺序排列，或报告无解。

特判掉 n\le 3 的情况。

$G$ 如下： 每种值建为左部点，每个位置建为右部点。 左右连边 $(i,j)$ 当且仅当 $i\ne j\ \land\ i\ne a_j$。 * * * 这样每个左部点的度 $\ge n-2$，对于左部大小为 $n-1$ 的点集，右部能连的大小必然 $\ge n-1\ ^{[\Delta]}$；左部大小为 $n$ 的点集（全集），右边能连的也为全集。 所以由 Hall 定理，$n\ge 4$ **必然有解**。 $[\Delta]$：反证法。若存在反例，则有 $n-1$ 个左部点不连边的点集均为相同的两个右部节点。而 $n\ge 4\implies n-1\ge 3$，综合不连边的条件，矛盾，原命题成立。 * * * 接下来随机多次排列 $\{p\}$（使用 `shuffle(...);`）直至合法即可。 要随多少次？别问我，问就是不知道。 猜一手当 $n$ 充分大的时候是两个排列的错排的概率是和 $n$ 无关的常数。