项链

标签：颜色 gcd 置换 旋转 项链 frac

项链在经过任意的旋转, 翻转, 颜色转换 (\(i \to i+1 \bmod m\))之后视作等价的。

统计有多少个本质不同的长度为 \(n\) 的项链, 对 \(998244353\) 取模。

---

首先旋转和反转是对下标的置换，经典结论是置换群的大小为 \(2n\) ，为 旋转 \(i\) 次 和 沿 \(i\) 对称。

然后颜色转化是对颜色的置换，共有 \(m\) 种。

两者结合得到最终的置换群，大小为 \(2nm\)

1. 旋转置换

设旋转 \(d\) 次，易得有 \(\gcd(d,n)\) 个类，每个类中元素个数为 \(k=\frac{n}{\gcd(d,n)}\)

每个类的第一个元素有 \(m\) 种选法，此时我们只需保证在颜色置换下等价即可，即 \(x k\equiv 0 \pmod m\) ，由结论知 \(x\) 的取值有 \(\gcd(k,m)\) 种。

最终得到：

\[\sum_{d|n}m^d\gcd(m,\frac{n}{d})\varphi(\frac{n}{d}) \]

2. 翻转置换

根据 \(n\) 的奇偶进行讨论，计算方法同上。

注意沿点对称时同时含有大小为 \(1\) 和 \(2\) 的类，此时 \(x\) 只能取 \(0\)

标签：颜色,gcd,置换,旋转,项链,frac
From： https://www.cnblogs.com/chihik/p/necklace.html