参考资料 ：

WeLikeStudying 的博客、群论简介 - OI Wiki

群论大概是抽象代数的一部分，所以我大概也说的不很具体。

或许我现在的能力不能解决专业的群论问题，但是群论的概念可以帮助我们更好地理解许多问题。我们对群论不应采取谈之色变的态度。

群

在数学中， 群 （group）是由一种集合以及一个二元运算所组成的，符合「群公理」的代数结构。

一个群包含一个集合 $S$ 和一个二元运算 $\times$,成为群 $G(S,\times)$。它应当满足以下性质 ：

  • 封闭性，即 $\forall a,b \in S,a \times b \in S$
  • 结合律，即 $\forall a,b,c \in S,(a \times b) \times c = a \times (b \times c) $
  • 单位元，即 $\exists e \in S,st \space \forall a \in S,a \times e = a$
  • 逆元，即 $\forall a \in S,\exists b \in S,st \space a \times b = e$

其中 $st$ 表“使得”义，为便于描述，下文中将群的二元运算称为乘法，但读者应当明确知道这种运算是自定义的，不应将其与代数中的乘法相混淆。

满足以上性质的集合和二元运算可以称为一个群，而有以上性质我们可以得到群的另外一些性质 ：

  • 单位元唯一，若有两个则乘积相等。
  • $a \times c = b \times c \rightarrow a = b$,同乘 $c$ 的逆元即得证。
  • 每个元素的逆元唯一，若有多个容易证明相等。
  • $\forall a \in S,\exists b \in Z,st \space a ^ b = e$，称这个 $b$ 为 $a$ 的阶，记作 $\text{ord}(a)$。

置换

置换是一个排列，表示的意义是把第 $i$ 个元素换到第 $p_i$ 个位置。

置换的乘法就是置换一次之后再置换一次，可以直接把这两个置换合成一个。

置换有单行表示和双行表示，更常见的大概是双行表示法。

双行表示长成这样 ：

第一行一般是顺序排列，第二行是上文所说的排列。

置换乘法得到的结果依然是置换。

置换的乘法满足结合律，但一般不满足交换律，具体可以手玩几个例子来感性理解。

置换的单位元也显然是上下两行相同。

置换的逆元容易找到，具体而言就是直接交换上下两行（怎么换过来的就怎么换回去）。

于是发现一个置换的集合和置换乘法可以构成一个群（但要注意这里的置换集合应当满足封闭性，即包含所有集合内元素相乘得到的置换）。我们把置换集合和置换乘法形成的群叫做置换群。

一个置换可以被拆成若干个环（循环），这里的环就是指若干数字的轮换。

为什么一定会被拆成若干环呢？

把置换看成一张有向图，于是每个点的入度和出度都为 $1$，图中允许存在自环。那么每个点一定在恰好一个环中，若不在环中，那么链的端点度数一定不合法，如果同时在两个环中，那么这两个环的额交点度数一定不合法。

于是一个置换一定可以被拆成若干个环，且每个环互不相交。

但是应当注意这个环是不稳定的，一个大环可能会分裂成若干小环。

我们可以通过一道题目来更深入地了解置换 ：

P4709 信息传递

简言之，置换意义下求 $n$ 次方根个数。这里的 $n$ 同时也是置换的元素个数。

这里的 $n$ 可能有什么性质，但是没看出来。

没什么思路的话就看看题解罢。

一个定理是 :

长度为 $m$ 的循环在 $k$ 次幂之后得到的置换有 $\gcd(k,m)$ 个等大小循环。

证明 ：

考虑我们怎么确定一个循环的大小，我们有一个不需要动脑子的做法 ： 沿着边走，走回来为止，经过的点数就是循环大小。换一种描述方式是这样的 ： 沿着循环每次走一步，走到原地为止，循环的大小就是走过的步数（容易发现这实际上是一个 $O(n)$ 做法，因为已经经过的点不需要再作为起点，每个点只会被经过恰好一次）。

但是现在的循环是原循环的 $k$ 次幂，这意味着我们在这里每走一步相当于在原循环中走 $k$ 步，因为每次乘法都向前走了一步。假设原循环的大小为 $m$，那么我们可以算出走回原地的步数是 $\frac{m}{\gcd(m,k)}$。因为走回原地时总的距离是 $\text{lcm}(m,k) = \frac{m \cdot k}{\gcd(m,k)}$，每一步的距离都是 $k$，于是走的步数是 $\frac{m}{\gcd(m,k)}$，对于每个元素而言都是这样，于是形成了 $\gcd(m,k)$ 个大小为 $\frac{m}{\gcd(m,k)}$ 的循环。

证毕。我并不擅长群论，所以这应当是一份通俗易懂的证明。

于是要求 $g$ 中的循环可以在 $n$ 步之后形成 $f$ 中的循环，首先大小得对的上。

我们反向理解，发现可以把 $f$ 中一些大小相等的循环拼起来得到 $g$ 中的一个循环，这样只要确定了一种拼接方案就可以确定一个 $g$。

于是考虑如何把 $f$ 中若干大小相同的循环拼接起来，根据上边的定理我们有了解决办法：

$f$ 中的 $r$ 个大小为 $s$ 的循环能拼接起来当且仅当 $\gcd(rs,n) = r$，直接套用上述定理即可得到。

因为置换乘法不满足交换律，这 $r$ 个元素的顺序将会影响最终得到的结果，于是其顺序不同时对答案的贡献应当是独立的。

我们应当注意置换内元素的排列顺序交换得到的置换是等价的，于是每个环的内部是无序的。

那么我们可以钦定第一个小环的第一个元素放在大环的第一个位置,。具体放在哪和钦定谁其实是一样的，但是不钦定的话就会看成不一样的从而算重，因为大环是循环同构的。

剩余的小环就要拼接到这个大环的后边

那么剩余的小环就可以任意排列，方案数为 $(r-1)!$

剩余的小环要断环为链，断点方案有 $s$ 种，于是总方案数是 $s^{(r-1)}$

那么方案数就是 $s^{(r-1)} (r-1)!$

发现长度不同的环不能拼接起来，那么就对于每个环长分开考虑，乘积就是最终答案。

设 $f_i$ 表示考虑了 $i$ 个循环时的答案，那么就有转移方程 ：

含义是对于前 $i$ 个循环，其可能被拆成合法的多个部分，那么枚举的 $r$ 就是当前这一部分的大小，这一部分的大小确定了，那么方案数就是从 $(i-1)$ 个中选择 $(r-1)$ 个的的方案数。原因是每一部分合成的大环之间是无序的（无论这些大环怎么排列，最终由环表示出的置换是相同的），于是不妨钦定每次都会选择第一个小环来去重，可以这样去重的原因是第一个小环只会出现在你当前的这一部分中，在之前没有出现过（把之前出现的第一个换成其他的某一个），那么每次更新之后的状态都是第一次出现，所以不会算重贡献。

于是我们枚举 $r$ 可以只枚举因数，总复杂度是 $O(n \tau(n))$。

那么这道题就做完了，我们更深入地了解了置换的概念与性质。

当我们学习新知识时应当力求完全理解，切不可囫囵吞枣，在那时舍弃的内容将永远不会出现在自己的思路中。

讲课时 ： 似乎还有其他同学准备了群论内容，那么我这边作为数学基础就只介绍到这里。

一些定义

在继续研究置换群的性质之前，我们要补充一些定义 ：

  • 不动点 ： 若 $k \times p = k$ 则 $k$ 是置换 $p$ 下的不动点，注意 $k$ 是一个元素而 $p$ 是一个置换。所有使 $k$ 成为不动点的置换 $p$ 构成的置换群 $Z_k$ 称为 $k$ 不动置换类，置换 $p$ 意义下的所有不动点 $k$ 构成集合 $C_p$。
  • 等价类 ： 对于一个元素 $k$ 和一个置换群 $G$，设元素集合 $E_k$ 表示 $k$ 通过置换群 $G$可以到达的所有元素的集合。一个性质是对于任意 $E_k$ 中的元素都可以由 $k$ 经过 $G$ 中的某一个置换到达。

Burnside引理

对于元素集合 $S$ 内元素形成的等价类个数 $l$，有 ：

自然语言描述就是等价类个数为各个置换下不动的元素个数的平均数。