polya定理板子
Luogu4980.
\(n\) 点环，每个点可以写 \(1 \ldots n\) 中的一个数，问有多少旋转后本质不同的染色方案。
\(\operatorname{burnside}\) 引理，仍然是考虑每个置换操作的等价类个数，发现对于一个往后 \(k\) 的置换，一共会构成 \(\gcd(n, k)\) 个环，环内部是同色，所以所求就是：
\[\begin{aligned} \sum _ {i = 1} ^ n n ^ {(n, i)} &= \sum _ {d \mid n} n ^ d \sum _ {i = 1} ^ n [(i, n) = d] \\ &= \sum _ {d \mid n} n ^ d \sum _ {i = 1} ^ {\lfloor \frac{n}{d} \rfloor} [(i, \frac{n}{d}) = 1] \\ &= \sum _ {d \mid n} n ^ d \varphi(\frac{n}{d}) \end{aligned} \]
枚举约数即可，暴力按照定义求 \(phi\)。
一定要记得 polya 定理最后要取平均值！
我不想就这样沦陷，迷失在黑夜，我将燃烧这生命，就算再壮烈。