Pólya定理

染色计数问题。

设有 $m$ 个颜色，对 $n$ 个元素染色。

Burnside 引理

对于每一个翻转操作，有 $s$ 个元素没有变化，所有的操作的平均值 $\bar s$ 即为所有本质不同的方案数。

Pólya 定理

求多少个方案没有变化时，对于一个操作，$n$ 个元素可以有 $t$ 组循环，那么不变的方案的数量为 $m ^ t$ 。

例题

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

共有 $n$ 种操作，对于旋转 $k(k \in [1, n])$ 个位置，可以发现可以分为若干组循环，如 $n = 6, k = 2$ 时，总是 $1, 3, 5$ 一起循环，$2, 4, 6$ 一起循环，具体地，每 $gcd(n, k)$ 一起循环。

接下来推式子
$$
\begin{aligned}
& \frac 1 n \sum _ {i = 1} ^ n m ^ {(n, i)} \\
= & \frac 1 n \sum _ {d | n} m ^ d \sum _ {i = 1} ^ n [(n, i) = d] \\
= & \frac 1 n \sum _ {d | n} m ^ d \sum _ {i = 1} ^ {\frac n d} [(\frac n d, i) = 1] \\
= & \frac 1 n \sum _ {d | n} m ^ d \varphi (\frac n d)
\end {aligned}
$$
暴力算即可。

查看代码

#include <cstdio>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int binpow (int b, int k)
{
    int res = 1;
    while (k)
    {
        (k & 1) && (res = (LL) res * b % mod);
        b = (LL) b * b % mod;
        k >>= 1;
    }
    return res;
}
int phi (int x)
{
    int res = x;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0)
                x /= i;
        }
    x > 1 && (res = res / x * (x - 1));
    return res;
}
int main ()
{
    int T;
    scanf("%d", &T);
    for (int n; T; T--)
    {
        scanf("%d", &n);
        int res = 0;
        for (int i = 1; i <= n / i; i++)
            if (n % i == 0)
            {
                (res += (LL)binpow(n, i) * phi(n / i) % mod) %= mod;
                i * i != n && ((res += (LL)binpow(n, n / i) * phi(i) % mod) %= mod);
            }
        printf("%lld\n", (LL) res * binpow(n, mod - 2) % mod);
    }
    return 0;
}