一、引入
前置声明：
-
本文章讲述了群论在
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)\) 的复杂度
