前置知识 Polya 定理。

会了以后推一下式子,得

$$
\begin{aligned}
ans &= \sum_{i=1}^n n^{\gcd(i, n)} \\
&= \sum_{d|n} n^d \varphi(\frac nd)
\end{aligned}
$$

直接做即可。没错我就是来水题解的

Polya 定理学习笔记

这个东西其实之前一直想学但是咕咕咕了 233.

Burnside 引理

$ans = { 1 \over |G| } \sum_{f \in G} C(f)$ ,其中 $C(f)$ 表示置换 $f$ 中不动点的个数

Polya 定理

定义 $L(f)$ 为置换 $f$ 的循环节数,可以理解为对于任意一种状态至多经过 $L(f)$ 次置换 $f$ 可以变回原样。

易证置换 $f$ 的不动点一定满足其自身的循环节为 $L(f)$ ,即 $C(f) = k^{L(f)}$ ,其中 $k$ 表示颜色种数。

Polya 定理的公式即 $ans = { 1 \over |G| } \sum_{f \in G} k^{L(f)} $ 。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×