浅谈置换和典型题目

· · 算法·理论

一 从一道简单黄题开始：P5151

(1)题目大意：

给定一个置换排列 A，对序列 1 \sim n 进行 k 次置换，求置换后的序列。

(2)前置知识：

现将序列每一位单独看成一个点。

如果若将原序列 1 \sim n 上的每一位元素（即置换序列下标）与置换序列上的每一位元素连上一条有向边，会形成若干个环，即原序列的每一个元素的置换是重复的。

如题目样例就会构成两个环：

这是很显然的，因为每一位的置换不会改变，所以只要一个元素第一次经过这一位后经 x 次置换第二次经过该位，就一定会再经 x 次置换第三次经过该位。

那么根据抽屉原理，一个元素最多经过 n 个不同的位置后就一定会重复经过某一位，这样就必定会构成一个环......吗？这道题是这样的，但也会有特殊情况，具体下文会给出解释。

(3)解题方法(具体代码请去看题解)：

  1. 方法一：暴力，找出每一个环的长度，对 k 进行取模即可，时间复杂度：\operatorname{O}(n)。
  2. 方法二：快速幂，因为先置换 a+b 次再置换 c 次和先置换 a 次再置换 b+c 次是一样，那么说明置换操作是满足结合律的，那么就可以仿照矩阵乘法一样，对置换序 A，进行一次快速幂，最后再对原序列进行一次置换即可，时间复杂度： \operatorname{O}(n \log k)。
  3. 方法三：倍增，先对原序列进行一次置换，设 f[i][j] 为第i个元素置换 2^j 次后的位置，那么易得公式 f[i][j]=f[f[i][j-1]][j-1]，再对 k 进行二进制拆分，若 k 在二进制下第 i 位为1，说明需要进行 2^i 次置换，直接调用即可，时间复杂度： \operatorname{O}(n \log k)。

(4).相似题目

UVA306：相当于每一位映射一个字母，可以将上一题的原序列看成本题字符串的下标。

二 另一道特殊一点的黄题：AT_abc367_e

(1)特殊之处：

为什么说这道题特殊呢？注意到P5151中置换序列是一个排列，说明置换序列中没有重复元素，而UVA306题目中更是直接给了

含有 n 个不同整数的数列

那么为什么置换序列元素互不相同很重要呢？因为如果置换序列元素互不相同，而下标显然也一定互不相同，那么将每一个元素抽象成点，从下标到元素连一条有向边，每一个元素的出度和入度一定都为 1，所以所构成的图像一定为一个环。

而本题却没有这样的约束，这会导致每一个元素出度一定为 1，而入度不一定为 1，所以图会变成环和内向基环树的混合体。

如下图即为一棵内向基环树：

然而有的时候，根节点的子树会全部退化成一条链，这样的图往往会有一些更特殊的性质：

再如本题样例一构成的图：

最左边那个奇怪的东西也是基环内向树。

不过第一题的三种解决方案，方法二和方法三仍然是可以直接使用的，而方法一就需要特判以环为根的树，再取模。

(2).相似题目：

AT_abc167_d： 这道题样例中的基环内向树更典型一点：

三 进阶挑战：

  1. AT_abc387_f

    题目大意：

    给定正整数 N 、 M 和长度为 N 的序列 A = (A_1, A_2, \dots, A_N) ，每个元素都是 1 和 N 之间的整数(含)。

求出长度为 N 的序列 x = (x_1, x_2, \dots, x_N) 的个数，每个元素都是 1 和 M 之间的整数(含)，满足以下条件：

最终答案对998244353取模。

我们还是将序列 A 视作置换序列，为了方便处理，令 A_i 向 i 连边，那么这样就又构成了一个基环外向图和环的杂交。

如样例三的图：

那么，我们只需构造出所有点权，使得 x_i\ge x_j 对于所有 i\to j 的边成立即可。

我们发现环上的点一定都是相同，那么考虑缩点，再树形DP一下就可以做出此题。

  1. AT_abc233_f

这道题又有所不同，令原排列为 p，我们应当将所有能够互换的 (u,v) 连边，这样可以构成许多连通块，若下标 i 和下标 p_i 不在同一个连通块，那么一定无解，然后再每个连通块中跑一遍最小生成树，然后优先满足叶子结点，再删去，如果做不到，即为无解。

四 一道黑题：AT_agc008_e

(以下图均来自官方题解，可以视为题解的补充)

直接从 a 考虑生成 p 比较难，那么，正难则反，我们不如考虑 p 变成 a 会发生什么。

首先，题目中说 p 为排列，那么显然从 i 连向

我们先观察其中一个环： ![](https://cdn.luogu.com.cn/upload/image_hosting/fdo9xhbn.png) 然后考虑 $a_i=p_i$ 和 $a_i=p_{p_i}$ 是什么意思： 显然如果将 $p$ 视作置换数组，那么 $a_i=p_i$ 就代表 $i$ 置换一步，$a_i=p_{p_i}$ 代表 $i$ 置换两步。 所以有以下四种情况： 1. 均为 $a_i=p_i$，则变换后的环仍为原环： ![](https://cdn.luogu.com.cn/upload/image_hosting/4eqybo8m.png) 2. 均为 $a_i=p_{p_i}$ 且原环为奇环，则变换后的环与原环同构： ![](https://cdn.luogu.com.cn/upload/image_hosting/4cvwewyl.png) 3. 均为 $a_i=p_{p_i}$ 且原环为偶环，则变换后的环分裂成两个大小相同的环： ![](https://cdn.luogu.com.cn/upload/image_hosting/o9plecvl.png) 4. $a_i=p_i$ 和 $a_i=p_{p_i}$ 杂交，则变成基环内向树： ![](https://cdn.luogu.com.cn/upload/image_hosting/i71fganu.png) 为何这道题只会形成**基环内向树**呢？我们来证明一下： 显然，这道题每个节点只能指向**下个节点**或**下下个节点**，则一个节点的入度一定小于等于2。那么如果根节点（此处根节点特指**环**）的子树不为链，那么说明该子树上的某个节点一定有且仅有2个子树，那么说明该节点的**上个节点**和**上上个节点**均指向了该节点，那么这个时候就不可能出现环了，因为如果要出现环，那么一个节点一定需要跨过**该节点、该节点的上一个节点、该节点的上上一个节点**，而这显然是不可能的，所以只会出现**基环内向树**。 那么，思路就很显然了： 1. 先从 $i$ 到 $a_i$ 连一条有向边，判断是**环**还或是**基环内向树**，如果都不是，则无解。 2. 先考虑**环**，那么对于每一种**相同大小**的环，设 $f_{i,j}$ 为大小为 $i$ 的环有 $j$ 个的方案数： - [ ] 不与前面融合： 若 $i$ 为奇数，即为奇环，则有可能是 $a_i=p_i$ 或 $a_i=p_{p_i}$ 两种情况：$f_{i,j}=f_{i,j}+2 \times f_{i,j-1}

否则，只有可能是 a_i=p_i，则 f_{i,j}=f_{i,j}+f_{i,j-1}

  1. 考虑基环内向树，由于 p 一定为环，所以考虑将链条串连到环内，如下图：

  1. 最后按照乘法原理乘起来即可。

五 总结

本篇文章大致介绍了置换的典型问题和解决方法，共4道黄题和1道黑题，由于本蒟蒻水平有限，可能会有一定的疏漏，还请各位大佬批评指正。