一、引入

前置声明：

• 本文章讲述了群论在 OI 中的一点简单运用

• 需要一定的图论、生成函数基础

• 如果有什么建议或意见，欢迎评论、私信！！！

T1 有标号项链计数

给定正整数 \(n,m\) 求用 \(m\) 种颜色染色一个长为 \(n\) 的项链的方案数，项链不能旋转

solution

答案显然是 $m^n$

哪个项链不能旋转？？？这道题明显脱离实际好吧

T2 无标号项链计数

给定正整数 \(n,m\) 求用 \(m\) 种颜色染色一个长为 \(n\) 的项链的方案数，项链可以旋转

solution

我们可以用所有 $\lceil$旋转 $i$ 次$\rfloor$ 的操作来将所有项链 $\lceil$去重$\rfloor$，我们要问的是去重后的不同项链个数。

以 \(n=4,m=2\) 为例：

\(\lceil\)旋转一次\(\rfloor\)串成环：

于是答案就是 \(6\)

我们于是需要一个巧妙的方法，让每个环都只算一次。

巧妙的方法：

我们对所有的项链 \(l\)，计算 旋转 \(r~(r\leq n)\) 次 后可以变成自己的 \(pair(l,r)\) 的个数

例子

将上图项链记为 \(l_1\)，那么就有 \(pair(l_1,2),pair(l_1,4)\) 满足条件

首先，我们计算对于每个项链，最少旋转 \(L\) 次可以变成自己

我们知道项链长为 \(n\)，很容易知道做 \(\exists k\in \mathbb{Z},kL = n\)，即可得到 \(L|n\)

那么一个 \(r\) 是合法的，当且仅当 \(L|r,r|n\)，那么一共就有 \(\frac n L\) 个合法的 \(r\)，而环中恰好有 \(L\) 个元素，所以每个环对答案的贡献恰好为 \(L\cdot\frac n L = n\)，计算这值后除以 \(n\) 就是答案。

然后，我们对每一个旋转 \(r\) 次的操作计算，有多少个项链 \(l\) 在 \(\lceil\)旋转\(r\)次\(\rfloor\) 的作用下不变，这就是\(\lceil\)旋转\(r\)次\(\rfloor\) 这个变换的不动点个数。

一个旋转操作会将项链分成若干个等价类，每个等价类的颜色必须相同，不同等价类间相互独立

例子

上图即为 \(n = 4,r = 2\) 时的 \(2\) 个等价类。

答案即为：

\[ans = \frac 1 n\sum\limits_{r=1}^nm^{\gcd(n,r)} \]

于是我们做到了 \(O(n)\) 的复杂度

二、