P4980
【模板】Pólya 定理
非常抱歉，群论的笔记全都记在笔记本上了。。。
所以只给定理加这题怎么做。
定理内容：
设有 $n$ 个元素，每个元素有 $m$ 种染色方法。设 $G$ 是 $n$ 个元素的置换群，则染色的总方案数为：
$$\dfrac{1}{|G|}\sum_{p\in G}T(p)$$
其中 $T(p)$ 表示在置换 $p$ 下，不动的染色方案数。
关于 $T(p)$ 的求法，设 $d(p)$ 为循环的个数，因为每个循环中必须染上同一种颜色，且不同的循环之间没有影响，所以我们能得到 $T(p)=m^{d(p)}$。
然后我们回到这个题目，我们的置换群可以这样表示：
$$\begin{pmatrix} 1 & 2 & \cdots & n-i & n-i+1 & \cdots &n\\ 1+i & 2+i & \cdots & n& 1 & \cdots & i\end{pmatrix}i\in [0,n)$$
显然置换群的大小 $|G|=n$。
然后我们得到式子：
$$\dfrac{1}{n}\sum_{i=1}^{n}n^{d(p_i)}$$
关于这个环的数量，暴力的话可以对每个置换建个图再跑个 SCC 什么的，复杂度就是 $O(n^2)$。
但显然不可以这么做。
我们仔细观察一波，比如打表手推眼瞪之类的方法，发现这里的 $d(p_i)=\gcd(n,i)$。
至于为什么，你发现环上跳 $i$ 步一直跳，跳回原点的步数就是 $\operatorname{lcm}(i,n)$，就是 $\dfrac{n}{\gcd(n,i)}$，而这是对于每个环来说的大小。所以环的个数自然就是 $\gcd(n,i)$。
然后就是那什么：
$$Ans=\dfrac{1}{n}\sum_{i=1}^{n}n^{\gcd(n,i)}$$
嗯？数论题的味道？开推：
$$\begin{aligned}=& \dfrac{1}{n}\sum_{i=1}^{n}\sum_{d\mid n}n^{d}[\gcd(n,i)=d]\\ = & \dfrac{1}{n}\sum_{d\mid n}\sum_{i=1}^{\frac{n}{d}}n^d[\gcd(n,i)=1]\\ =& \dfrac{1}{n}\sum_{d\mid n}n^d\sum_{i=1}^{\frac{n}{d}}[\gcd(n,i)=1]\end{aligned}$$
$\sum_{i=1}^{\frac{n}{d}}[\gcd(n,i)=1]$ 是啥，是 $\varphi(\dfrac{n}{d})$ 啊。
然后不就是：
$$\begin{aligned}=& \dfrac{1}{n}\sum_{d\mid n}\varphi(\dfrac{n}{d})n^d\end{aligned}$$
不会化了。
所以直接躺平，大力求解 $\varphi$，最后时间复杂度大概是 $O(T\sqrt{n}(\sqrt{n}+\ln n))$，好像这个复杂度比较出事，但实际上远远跑不到，很轻松就过掉了。
如果想要变快，可以记忆化 $\varphi$。什么，不知道这么大怎么记忆化？map 或者 Hash 随便挑一个用就完了，然后复杂度就对了。
代码：
1 |
|