「Summary」2023-01-31 做题记录

抽象。

$\mathtt{Burnside}$

$\mid X/G \mid = \frac{1}{\mid G \mid} \sum_{g \in G} X^{c(g)}$

$\mathbb{P4890}$

这个是板题，直接代入原式可以得到 $ans = \frac{1}{n}\sum_{k=0}^{n-1}n^{\gcd(k, n)}$ 。
简单解释一下，在旋转 $i$ 次下的置换，总长是 $ni$ ，一个循环的长度为 $\mathrm{lcm}{(n,i)}$ ，那么循环节节数即是 $c$ 为 $\frac{ni}{\mathrm{lcm(n, i)}}= \gcd(n, i)$ 。
然后继续化简原式子为。

$$ \begin{aligned} ans &= \frac{1}{n}\sum_{k=0}^{n-1}n^{\gcd(k, n)} \\ &= \frac{1}{n} \sum_{d \mid n}n^{d}\sum_{k=0}^{\frac{n}{d}}[\gcd(n, k) = 1] \\ &= \frac{1}{n} \sum_{d \mid n}n^{d} \varphi(\frac{n}{d}) \\ \end{aligned} $$

可以直接做了。

$\mathbb{P1446}$

$\mathbb{POJ2888}$

对于一个置换 $P(i)$ ，令其不动点个数为 $\gcd(n, i)$ 把方案数记为 $f(\gcd(n, i))$ ，答案为 $\frac{1}{n} \sum_{i=1}^{n} f(\gcd(n, i))$