mydcwfy's Blog

群论和 Pólya 定理

Posted on
Symbols count in article: 4.4k Reading time ≈ 10 mins.

本章节不再讲述非常难的群论基础，仅作为学习 Pólya 的工具，基本不涉及证明。

群论和 Pólya 定理

1. 群论基础

1）置换

其实就是一个函数，或者是映射。

我们首先有一个 $1\sim n$ 的排列，然后我们将顺序打乱，然后前后的变化就是一个置换。

写为标准的格式，就是

2）循环置换

就是将一个置换循环（？）。

具体来说，就是 1 变 2，2 变 3，…，$n-1$ 变 $n$，$n$ 变 1。

这样大概理解了吧。

我们将其投射到图上，会发现每一个置换可以看作一张图中沿有向图的方向行走一个。

循环置换中，就是 1 连 2，2 连 3，这样，就会构成一个环。

每一个置换都是有几个环构成的。

3）置换群

就是所有置换的集合。

注意，他的子集也可以是置换群。

2. Burnside 引理

求解的问题是某类本质不同的方案数。

本质相同比如：翻转、旋转能重合的。

引理：不同方案数就是每个置换的不动点的平均值。

首先，这里的置换就是从一个方案转换到另一种方案的过程。

这里可能有一些抽象，后面结合例题一起来看。

比如，我们看一个简单的例子。

给定一串珠子，给它染上 3 种颜色，求本质不同的方案数。

置换过后，如果该方案是没有变化的，那么就称该方案在该置换下是不动点。

我们对于每一个置换，都求一下不动点的个数，最后求一下平均值，就是本质不同的方案数。

3. Pólya 定理

刚才的 Burnside 引理，还需要求不动点。

首先，我们将这个置换拆成多个循环。

然后，对于每一个循环，我们只要染上同一种颜色，就是不动点。

所以，不动点个数就为 $c^k$，其中 $c$ 表示颜色，$k$ 表示循环数。

这样，我们只需要求每一个置换的循环数，就可以求出不动点了。

4. 例题

T1：串珠子/【模板】Pólya 定理

题目传送门 Luogu

第一种：旋转。

可以旋转 0 格，1 格，……，$n-1$ 格。

那么，$k$ 格之后，$x$ 会转到 $x+k$ 的位置。

设 $d=\gcd(n,k)$，那么转 $\dfrac{n}{d}$ 次后就会产生重叠，所以循环节长度就为 $\dfrac{n}{d}$。

于是，画个图就可以理解，一共有 $d$ 个循环节。

所以，不动点就为 $m^{\gcd(n,k)}$。

第二种：翻转。

首先，我们要分类。

如果 $n\equiv1\pmod2$，于是对称轴一定穿过每个点。

就有 $n$ 种情况，每一种情况的循环个数为 $1+\dfrac{n-1}{2}=\dfrac{n+1}{2}$。

如果 $n\equiv0\pmod2$，于是对称轴可能是穿过每个点，或者是穿过两个点的中间。

如果对称轴穿过一个点，就是 $2+\dfrac{n-2}{2}=\dfrac{n}{2}+1$。

如果对称轴穿过中间，就是 $\dfrac{n}{2}$。

至此，我们就将所有不动点的情况全部计算了出来。

（这是 Luogu 的代码，还要出来一下 后面的公式推导）

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
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const ll Mod = 1e9 + 7;

ll Gcd(ll a, ll b)
{
    if (!b) return a;
    return Gcd(b, a % b);
}

ll qpow(ll a, int b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res *= a, res %= Mod;
        a *= a;a %= Mod;
        b >>= 1;
    }
    return res;
}

int get_phi(int n)
{
    int ans = n;
    for (int i = 2; i <= n / i; ++ 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;
}

int main()
{
    int t, n;cin >> t;
    while (t --)
    {
        scanf("%d", &n);
        ll ans = 0;
        for (int i = 1; i <= n / i; ++ i)
            if (n % i == 0)
            {
                ans = (ans + qpow(n, i) * get_phi(n / i) % Mod) % Mod;
                if (i * i != n) ans = (ans + qpow(n, n / i) * get_phi(i) % Mod) % Mod;
            }

        printf("%lld\n", ans * qpow(n, Mod - 2) % Mod);
    }
    return 0;
}

T2：魔法手链

题目传送门 AcWing

这道题，我们不能使用 Pólya 定理，因为 Pólya 不能满足这些限制。

于是，我们使用 Burnside 引理。

怎样找不动点呢？

首先，我们考虑 $k$ 旋转之后得到的置换。

然后，对于每一个点，我们都有每 $d=\gcd(n,k)$ 都是当前点可能达到的。

于是，我们如果要不动点的话，这每 $d$ 个点出现一次的点一定都要相等。

纵观全局，这个循环是 $\dfrac{n}{d}$ 长度的。

于是，就是 $d$ 个互不相同的循环。

问题就变为了 $0\sim d-1$ 的颜色将会被复制 $\dfrac{n}{d}$ 次使得填满该环。

于是，我们只需要关注这个小段即可，而且他首尾相连。

也就是长度为 $d$ 的环染色数量就是不动点的数量。

这样，我们可以考虑 DP 了。

首先，我们初始化，首先定义 $d$ 的颜色，枚举即可。

然后，我们直接暴力枚举每一种颜色和前面的颜色，只要可以放在一起就累计答案。

最后，取 $d$ 的颜色的累计答案，就可以了。

但是，本题 $n\leq10^9$，无法通过。

所以，我们可以预处理长度为 $1\sim n$ 的环的答案。

这个就是一个简单的矩阵快速幂优化 DP 了。

但是，本体中，我们还不能枚举 $k$。

观察到 $k$ 的答案仅与 $d$ 的取值相关。

所以，我们枚举 $d|n$，然后找到 $k=k’*d$ 使得 $k’$ 与 $\dfrac nd$ 互质。

这不就是 $\varphi(\dfrac nd)$ 吗！

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 11, Mod = 9973;
int M;

class Matrix{
public:
    int a[N][N], n, m;
    inline void clean(int _n, int _m)
    {
        memset(a, 0, sizeof a);
        n = _n, m = _m;
    }
    const Matrix operator *(const Matrix &b)const{
        Matrix c;c.clean(n, b.m);
        if (m != b.n) return c;
        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= b.m; ++ j)
                for (int k = 1; k <= m; ++ k)
                    c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j]) % Mod;
    }
    const Matrix operator ^(int x)const{
        Matrix res, tmp = *this;res.clean(n, m);
        for (int i = 1; i <= n; ++ i) res.a[i][i] = 1;
        while (x)
        {
            if (x & 1) res = res * tmp;
            x >>= 1;
            tmp = tmp * tmp;
        }
        return res;
    }
}F0, ed;

int get_phi(int n)
{
    int ans = n;
    for (int i = 2; i <= n / i; ++ 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;
}

inline int qpow(int a, int k)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * a % Mod;
        a = a * a % Mod;
        k >>= 1;
    }
    return res;
}

inline int inv(int x){return qpow(x, Mod - 2);}

inline int calc(int x)
{
    ed = F0 ^ x;
    int sum = 0;
    for (int i = 1; i <= M; ++ i) sum += ed.a[i][i], sum %= Mod;
    return sum;
}

int main()
{
    int t, n, k;cin >> t;
    while (t --)
    {
        cin >> n >> M >> k;
        F0.clean(M, M);
        for (int i = 1; i <= M; ++ i)
            for (int j = 1; j <= M; ++ j) F0.a[i][j] = 1;

        while (k --)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            F0.a[x][y] = F0.a[y][x] = 0;
        }

        int res = 0;
        for (int i = 1; i <= n / i; ++ i)
            if (n % i == 0)
            {
                res = (res + calc(i) * (get_phi(n / i) % Mod) % Mod) % Mod;
                if (i == n / i) continue;
                res = (res + calc(n / i) * (get_phi(i) % Mod) % Mod) % Mod;
            }
        cout << res * inv(n) % Mod << endl;
    }
    return 0;
}