警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「洛谷 P4980」Polya 定理

题意

传送门:洛谷 P4980 - Polya 定理

给定一个 \(n\) 个点,\(n\) 条边的环,有 \(n\) 种颜色,给每个顶点染色,问有多少种本质不同的染色方案,答案对 \(10^9+7\) 取模。

注意本题的本质不同,定义为:只需要不能通过旋转与别的染色方案相同。

\(1\le n\le10^9,1\le t\le10^3\)

解法

Polya 定理模板题。

给一个集合 \(X\) 和一个置换群 \(G\)\(|X|=n\)。用 \(m\) 种颜色染色,本质不同的方案数 \(\displaystyle L=\frac1{|G|}\sum_{g\in G}m^{c(g)}\)

其中 \(c(g)\) 是置换 \(g\) 的循环节长度。

然后就开始推式子了:

\[ \begin{aligned} &L\\ =&\frac1{|G|}\sum_{g\in G}m^{c(g)}\\ =&\frac1n\sum_{i=1}^{n}m^{\gcd(i,n)}\\ =&\frac1n\sum_{d|n}m^d\sum_{i=1}^n[\gcd(i,n)=d]\\ =&\frac1n\sum_{d|n}m^d\sum_{i=1}^{n/d}[\gcd(i,n/d)=1]\\ =&\frac1n\sum_{d|n}\varphi(n/d)m^d\\ \end{aligned} \]

代码