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 定理最後要取平均值！
我不想就這樣淪陷，迷失在黑夜，我将燃燒這生命，就算再壯烈。