Polya定理，常用于计数。

        在介绍Polya定理前，需要有一些前缀知识。

群

        群是一种代数系统。对于一个非空集合和定义在它上面的运算组成的系统称为代数系统。这里定义集合为$S$，运算为$*$。
        群满足以下条件：

  • 封闭性。对于任意$a\in S,b\in S$，有$a*b\in S$。
  • 满足结合律。即有$a*(b*c)=(a*b)*c$。
  • 存在幺元。即有$e\in S$，满足$a*e=e*a=a$。
  • 存在逆元。即对于$a\in S$，存在$a^{-1}\in S$满足$a*a^{-1}=e$。

        注意群不一定满足交换律。

置换与置换群

        对于1~n这n个元素的一个排列，通过(1~n)->(1~n)元素的一一映射关系得到另一个排列，称为一个置换。下面就表示一个置换：

        对于n个元素，其n!个不同的置换组成集合$S$。定义$\bigodot$表示置换的左复合运算，即对于$x,y\in S$，有$x\bigodot y$表示对这n个元素先应用x置换，再应用y置换。比如：

        可以证明$S$与运算$\bigodot$形成一个群，这个群的任一子群称为置换群。

Burnside引理

        对于集合$S$和其置换群，由该置换群上的置换诱导形成的等价关系必然可以将$S$划分为若干个等价类。这里的直观理解是：当$S$上的一个元素可以通过置换群中的置换操作得到另一个元素，则它们在一个等价类中。计算等价类数量是一个具有实际意义的问题。
        如果一个元素经过某一个置换$P$得到它本身，则称该元素为置换$P$下的不动点。
        【Burnside（伯恩赛德）引理】由S的置换群<$G,\bigodot$>诱导的等价关系将$S$划分所得的等价类数目等于：

        $\psi(\pi)$为置换$\pi$的不动点数目。

Ploya定理

        Burnside定理确实可以计数，但是时间复杂度高，这里就引入了Polya定理。
        这里用一个实际例子：给定一个含有n个珠子串起来的环，用m种不同的颜色给它们染色，有多少种本质不同的染色方案？这里的本质不同是指不能通过旋转得到另一个染色方案。
        在这个问题里，我们对n个珠子从上面开始，顺时针编号1~n，这就是一个排列。它可以通过旋转这一种置换得到另一个排列，比如对于n=4时，起初排列为：1、2、3、4，顺时针旋转一个单位得到排列4、1、2、3，这是一个置换。这同时说明1、2、3、4与4、1、2、3在一个等价类中。
        在一个置换中，如果将1~n看成点，映射关系看成有向边，则得到了一个有向图。我们定义有向图中强连通分量的数目为该置换的循环节数目，每一个强连通分量就称为循环节。
        为了应用Burnside引理，下面考虑如何求置换的不动点数目。
        如果一种染色方案经置换$\pi$后不变，那么该置换每一个循环节内部点的颜色必然相同，不同循环节的颜色互不干扰。如果定义$c(\pi)$为置换$\pi$的循环节数目，显然不动点数目就是$m^{c(\pi)}$。
        这时应用Burnside引理可以得到等价类数目：

        这就是总的方案数，同时我们也得到了Polya定理的表达形式。
        在旋转中，可以得到一个结论：旋转k步对应置换的循环节数目为$gcd(k,n)$。除了旋转还有翻转这一个置换类型，有结论：n为奇数时，循环节数目为$\frac {n} {2}+1$；n为偶数时，若翻转线穿过珠子，则为$\frac {n} {2}+1$，否则为$\frac {n} {2}$。

示例模板

        模板题：戳这里。
        这里只有旋转操作，应用Polya定理，答案即为：

        这里的置换定义为：不旋转、顺时针旋转1位、…、顺时针旋转n-1位，它们满足群的性质。
        但是求解这个求和式的时间复杂度是$O(n)$的，容易TLE，考虑优化。
        枚举$gcd(i,n)$，得到：

        $\phi(x)$是欧拉函数，这里用定义式去求解，总体时间复杂度为$O(\sqrt n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>

#define MOD (1000000000+7)
using namespace std;
typedef long long ll;

ll euler(int x) {//求欧拉函数
    ll ans = 1;
    for (ll i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            ans *= (i - 1), x /= i;
            while (x % i == 0)ans *= i, x /= i;
        }
    }
    if (x > 1)ans *= (x - 1);
    return ans;
}

ll qPow(int a, int b) {//快速幂
    ll ans = 1, s = a;
    while (b > 0) {
        if (b & 1)ans = (ans * s) % MOD;
        s = (s * s) % MOD, b >>= 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    int t, x;
    ll inv, ans;
    cin >> t;
    while (t--) {
        cin >> x;
        inv = qPow(x, MOD - 2);//逆元
        ans = 0ll;
        for (int i = 1; i * i <= x; i++) {
            if (x % i == 0) {
                ans = (ans + euler(i) * qPow(x, x / i)) % MOD;
                if (i * i != x)ans = (ans + euler(x / i) * qPow(x, i)) % MOD;
            }
        }
        ans = ans * inv % MOD;
        cout << ans << "\n";
    }
    return 0;
}