西电校赛遇到的神秘题目。

题目

称长度为 $n$ 的排列 $p$ 是完美的，当且仅当对于任意 $1 \leq i < j \leq n$，$p_i \perp p_j$ 当且仅当 $i \perp j$（这里的垂直符号代表互素）。

给定正整数 $n$ 满足 $n \leq 10^6$，请求出长度为 $n$ 的完美的排列的总数，对 $10^9+7$ 取模。

初步思考

注意到恒等排列 $p_i \equiv i$ 一定合法。

考虑用交换构造出所有排列。什么交换是不合法的呢？

对于两个位置 $i, j$，如果有另一个位置 $k$ 与 $i$ 不互素而与 $j$ 互素，或反之（即 $k$ 与 $i$ 和 $j$ 的互素性不同），则称 $k$ 是能区分 $i$ 和 $j$ 的一个证人。

如果 $i$ 和 $j$ 有证人，则我们不能随意交换它们，否则与那个证人之间的互素关系就会发生变化。

反之，我们可以任意交换放在这两个位置上的数。

我们称两个位置没有证人为“同类”。注意到这个关系具备传递性，从而是等价关系。

那么这些位置上能放的数字就是相同的集合，可以任意排列。

刻画同类关系。注意到两个数是同类，当且仅当它们的质因子集合是相同的。

于是不难想到用无平方因子数作为一类数的代表元。线性筛预处理每个位置的代表元。

预处理阶乘。

发现有另一类可能的变换：对于大于 $n/2$ 的素数，能区分它们和其他数的证人太大，所以这些数以及 1 之间是同类的。

实现以上所有的逻辑。

然后，我们惊喜的发现代码能够通过 $n=20$，却在 $n=500$ 时莫名其妙的 WA 了。

完整结论

考虑两个素数 $p, q$ 满足 $\lfloor n/p \rfloor = \lfloor n/q \rfloor$。

我们可以完整地交换它们的所有倍数。换言之，对于 $a = k_1 p$ 和 $b = k_2 q$，我们可以令 $p_a = k_1 q$，$p_b = k_2 p$，得到的排列仍然合法（是“完美的”）。

实现这个逻辑。然后就对了

正解思路

上面的补丁看上去毫无逻辑，完全不能理解为什么这是对的。同时，我们也不能理解为什么没有其他的自由度。

在最初的思路上继续尝试是没有前途的。正解有完全不同的另一种视角。

考虑互素图。这是一个有 $n$ 个节点，标号为 $1, 2, 3, \cdots n$ 的无向图。对于两个节点 $i, j$，它们之间有边当且仅当 $i \perp j$。

以及它的补图非互素图：对于两个节点 $i, j$，它们之间有边当且仅当 $i \not \perp j。$

我们的任务本质上是对这个图进行图自同构计数。

解释一下概念：两个图 $G_1, G_2$ 的一个同构 $f$ 是一个从 $G_1$ 的点集到 $G_2$ 的点集的映射，满足 $\forall u, v \in G_1, (f(u), f(v)) \in G_2 \Leftrightarrow (u, v) \in G_1$，即映射后的点之间有边等价于原来的点之间有边。

自同构就是 $G_1=G_2$ 时的图同构。

接下来，我们将运用一个重要的性质：图同构保持点邻域的包含关系。

我们定义一个点的邻域 $N(u)$ 是这个点本身，以及所有与之有边相连的点所构成的集合：

$$ N(u) = \{ u \} \cup \{v \mid (u, v) \in G \} $$

我们需要证明的是：对于 $G_1$ 与 $G_2$ 的图同构 $f$，$\forall u, v \in G_1, N(u) \subseteq N(v) \Leftrightarrow N(f(u)) \subseteq N(f(v))$。

证明的方法是考虑定义。首先我们有 $N(f(u)) = f(N(u))$，因为对于每个和 $u$ 有边相连的点，同构之后的点根据定义也必然和 $u$ 同构之后的点有边。而对于和 $u$ 没有边相连的点，根据定义，同样在同构之后也不会和 $f(u)$ 有边。

于是，我们相当于要证明 $f(N(u)) \subseteq f(N(v))$。这是显然的，因为对于一个元素 $x \in N(v)$，$f(N(v))$ 中一定把原来在 $N(v)$ 中的 $x$ 变成了 $f(x)$，这是由“映射作用于集合”的定义决定的。

有了这个引理之后，我们就知道了一点：我们一定不能把素数和合数相互映射。因为素数不包含任何其他点的邻域，而合数包含其他点的邻域，这样的交换会破坏掉邻域的包含关系，必定不合法。

于是我们应当分别考虑素数与合数之间各自的置换关系。

在素数中，我们考虑一个简单的限制：每个点 $u$ 的对应点 $f(u)$ 的邻域大小（即度数加一）必定和 $N(u)$ 的大小一样。

做完这个限制之后，素数之间就可以任意置换了吗？

暂时搁置疑问。假设确定了素数的置换，我们考虑合数的置换。

运用邻域包含引理。对一个合数 $x$，$f(x)$ 的每一个质因子 $p$ 都一定有一个 $x$ 的质因子 $q$ 与之对应，满足 $f(q)=p$，反过来也成立。即，$f$ 是 $x$ 与 $f(x)$ 的质因子集合间的一一对应。

这是容易理解的。

对于相同的质因子集合，考虑我们最初的想法。不难发现它们之间可以任意互相交换。所以，确定了素数的置换之后，我们一定会有一堆合法的合数置换，满足我们最初的想法。

这一步有点类似上下界的思想：我们先找出了一个必要条件，之后发现这是充分的。

如果直接这么写，会当场倒闭，连样例都过不去。那么我们的推理中哪里缺失了呢？

我们分类讨论了质数与合数，但唯独没有讨论 1。

其实，1 在这里的地位和素数是类似的：它的邻域不包含其他任何数的邻域。

所以自然遵循和素数同样的规则：可以与任意度数相同的素数互相交换。注意到 1 与任何数都互素，所以它在非互素图中的度数是 0，也就只能和那些度数为 0，即大于 $n/2$ 的素数相互交换了。

至此，这个题就做完了。