题解 P4980 【【模板】Polya定理】
GKxx
2019-07-28 00:09:07
### 题意
$n$个点的环，用$m$种颜色给点染色，求本质不同的方案数。
两个方案本质相同，当且仅当其中一个方案可以通过旋转得到另一个。
### 题解
一种染色方案可以看做先染了前$d$个位置，然后将这一段复制$n/d$次拼接而成，其中$d$是$n$的约数。我们称这个$d$为一种染色方案的*周期*（这里默认是最小正周期）。
对于一个周期为$d$的染色方案，将它旋转$d$次会得到$d$个看起来不同但本质相同的染色方案。
设$f(x)$表示周期为$x$的看上去不同的方案数。枚举周期$d$，那么每一种周期的方案就多算了$d$次，因此
$$ans=\sum\limits_{d|n}\frac{f(d)}{d}$$
$f(x)$不容易计算，但是我们知道：对于$n$的所有约数$d$，将$f(d)$求和就会得到总方案数$m^n$，即
$$m^n=\sum\limits_{d|n}f(d)$$
莫比乌斯反演得
$$f(x)=\sum\limits_{d|x}\mu(x/d)m^d$$
代入第一个式子得到
$$ans=\sum\limits_{d|n}\frac{1}{d}\sum\limits_{k|d}\mu(d/k)m^k$$
$$=\sum\limits_{d|n}\frac{d}{n}\sum\limits_{k|\frac{n}{d}}\mu(n/dk)m^k$$
$$=\frac{1}{n}\sum\limits_{d|n}d\sum\limits_{k|\frac{n}{d}}\mu(n/dk)m^k$$
$$=\frac{1}{n}\sum\limits_{k|n}m^k\sum\limits_{d|\frac{n}{k}}d\mu(n/dk)$$
$$=\frac{1}{n}\sum\limits_{k|n}m^k\varphi(n/k)$$
上面设颜色的数量为$m$是为了避免混淆，本题中$m=n$。
本题对于等价类的定义是相当简单的，因此可以用莫比乌斯反演轻松解决。如果遇到更加复杂的等价类定义就要老老实实使用polya计数了。
```cpp
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
template <typename T> inline void read(T& x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
typedef long long LL;
const LL mod = 1e9 + 7;
inline LL qpow(LL x, LL k) {
LL s = 1;
for (; k; x = x * x % mod, k >>= 1)
if (k & 1) s = s * x % mod;
return s;
}
inline LL phi(LL x) {
LL ans = x;
for (LL i = 2; i * i <= x; ++i)
if (!(x % i)) {
ans = ans / i * (i - 1);
while (!(x % i)) x /= i;
}
if (x > 1) ans = ans / x * (x - 1);
return ans;
}
int main() {
int T; read(T);
while (T--) {
LL n; read(n);
LL ans = 0;
for (LL k = 1; k * k <= n; ++k)
if (!(n % k)) {
if (k * k == n)
ans = (ans + qpow(n, k) * phi(n / k) % mod) % mod;
else {
ans = (ans + qpow(n, k) * phi(n / k) % mod) % mod;
ans = (ans + qpow(n, n / k) * phi(k) % mod) % mod;
}
}
writeln(ans * qpow(n, mod - 2) % mod);
}
return 0;
}
```