洛谷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;
}