洛谷P4980 【模板】Polya 定理题解

题意：

给定一个 $n$ 个点，$n$ 条边的环，有 $n$ 种颜色。

给每个顶点染色，问有多少种本质不同的染色方案，答案对 $10^9+7$ 取模

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

输入格式：

第一行输入一个 $T$，表示有 $T$ 组数据

第二行开始，一共 $T$ 行，每行一个整数 $n$，意思如题所示。

输出格式:

共 $T$ 行，每行一个数字，表示染色方案数对 $10^9+7$ 取模后的结果。

数据范围：

$1\le T \le 10^3, ~1 \le n \le 10^9$

传送门：Pólya 定理（在这篇文章里讲解了推导过程）

首先先把 Burnside 引理复习一下。

Burnside 引理

设 $A,B$ 为有限集合，$X$ 为一些从 $A$ 到 $B$ 的映射组成的集合（这可以视作直接染色）。

$G$ 是 $A$ 上的置换群，且 $X$ 中的映射在 $G$ 中的置换作用下封闭。

$X / G$ 表示 $G$ 作用在 $X$ 上产生的所有等价类的集合¹（即本质相同的染色方案），则

$|X / G|=\frac{1}{|G|} \sum_{g \in G}\left|X^g\right|$

其中 $X^g=\{x \mid x \in X,~g(x)=x\}$ ，也就是在置换 $g$ 下的不动点构成的集合。

考虑原题中的旋转操作，其对应 Burnside 引理中的置换群 $G$ ，而 $X$ 即为染色操作。

因此我们需要找到对于置换「 $g=$ 旋转 $k$ 次」，它的不动点有几个（也就是旋转 $k$ 下后本质不变的染色方案）

显然旋转 $k$ 次不动意味着染色方案存在长为 $a(a \mid k)$ 的循环节。

又因为 $a \mid n$ ，所以 $a \mid \gcd(k,n)$ ，于是我们可以改为判定存在一个长度为 $\gcd(k,n)$ 的循环节。

对于 $g=$ 旋转 $k$ 次，实际上每个子串前 $\gcd(k,n)$ 格都是可以任意取的，因此贡献为 $n^{\gcd(k, n)}$ 。

于是答案即为

$\frac{1}{n}\sum_{k = 1}^n n^{\gcd(k, n)}$

换一个枚举方式

$\frac{1}{n}\sum_{d \mid n} n^d \sum_{k=1}^n [\gcd(k, n) = d]$

用一下莫比乌斯反演的套路

$\begin{aligned} &\frac{1}{n}\sum_{d \mid n} n^d \sum_{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor} \left[\gcd\left(k, \left\lfloor \frac{n}{d}\right\rfloor\right) = 1\right] \\[6pt]=& \frac{1}{n}\sum_{d \mid n} n^d\varphi\left(\frac{n}{d}\right) \end{aligned}$

另外在本题中可以直接暴力求 $\varphi$ ，时间复杂度为 $\mathcal{O}(Tn^{\frac{3}{4}})$ 。

到这里其实就完成这道题了，不过我们从推导中可以进一步得到 Pólya 定理。

我们把置换 $g$ 写作如下形式

$\left(\begin{array}{cccc}1&2&\cdots&k\\a_1&a_2&\cdots&a_k\end{array}\right)$

考虑将 $i$ 与 $a_i$ 连边，显然全部操作后会出现若干个环，并且这些环的颜色是相同的。

于是我们可以得到 Pólya 定理：

在与 Burnside 引理相同的前置条件下，若 $X$ 为所有从 $A$ 到 $B$ 的映射，则

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

其中 $c(g)$ 表示置换 $g$ 能拆分成的不相交的循环置换的数量（也就是我们刚才说的那些环的数量）

好好好，代码在这：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)())

int qpow(int a, int b)
{
    int r = 1;
    while(b)
    {
        if(b & 1) r = r * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return r;
}
int phi(int n)
{
    int ans = n;
    for(int i = 2; i * i <= n; i++)
        if(n % i == 0)
        {
            ans = ans / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    if(n > 1) ans = ans / n * (n - 1);
    return ans;
}
void solve()
{
    int n, res = 0; cin >> n;
    for(int i = 1; i * i <= n; i++)
        if(n % i == 0)
        {
            add(res, phi(i) * qpow(n, n / i) % mod);
            if(i * i != n) { add(res, phi(n / i) * qpow(n, i) % mod); }
        }
    cout << res * qpow(n, mod - 2) % mod << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}