本课时有配套视频讲解，购买后即可观看（永久有效）
等价类
一、课上练习
编程练习
（暂无）
二、知识总结
✨ 核心思想
等价类是抽象代数中的基础概念，它提供了一种将集合中"本质相同"的元素归为一组的方法。在竞赛中，等价类思想可以简化计数问题——把等价的对象合并后只数不同的类。Burnside 引理则给出了在群作用下计数不等价对象（即等价类个数）的优雅公式。
✨ 等价关系
定义：集合 S 上的一个关系 ~ 称为等价关系，如果它满足：
- 自反性：对所有 a 属于 S，a ~ a
- 对称性：对所有 a, b 属于 S，若 a ~ b 则 b ~ a
- 传递性：对所有 a, b, c 属于 S，若 a ~ b 且 b ~ c 则 a ~ c
等价类：元素 a 的等价类 [a] = {b 属于 S | b ~ a}，即与 a 等价的所有元素组成的集合。
划分定理：等价关系将集合分成若干互不相交的等价类，所有等价类的并集就是整个集合。反过来，集合的每个划分也定义了一个等价关系。
✨ 等价关系的常见例子
- 模运算：整数集上，a ~ b 当且仅当 a ≡ b (mod n)。等价类就是模 n 的剩余类 [0], [1], ..., [n-1]。
- 旋转等价：将圆上 n 个位置的着色方案中，通过旋转可以相互得到的方案视为等价。
- 图同构：两个图的顶点之间存在双射使得邻接关系保持，则两图等价。
- 字符串循环同构：若字符串 B 可以通过 A 的循环移位得到，则 A ~ B。
✨ Burnside 引理
问题背景：有一个群 G 作用在集合 X 上（如旋转群作用在着色方案上），求不等价的对象个数（即等价类的个数）。
Burnside 引理：
等价类个数 = (1/|G|) × Σ(g 属于 G) |X^g|
其中 |X^g| 表示在变换 g 下保持不变的元素个数（称为 g 的不动点数）。
直觉：每个等价类中的元素被所有变换"固定"的总次数恰好等于群的大小 |G|，所以所有不动点数之和除以 |G| 就是等价类个数。
✨ 代码实现
Burnside 引理：旋转等价的项链计数
1#include <iostream>
2using namespace std;
3typedef long long ll;
4
5// 问题：用 c 种颜色给 n 个珠子的项链着色
6// 旋转视为等价，求本质不同的方案数
7
8ll qpow(ll base, ll exp, ll mod) {
9 ll result = 1;
10 base %= mod;
11 while (exp > 0) {
12 if (exp & 1) result = result * base % mod;
13 base = base * base % mod;
14 exp >>= 1;
15 }
16 return result;
17}
18
19ll euler_phi(ll n) {
20 ll result = n;
21 for (ll i = 2; i * i <= n; i++) {
22 if (n % i == 0) {
23 result = result / i * (i - 1);
24 while (n % i == 0) n /= i;
25 }
26 }
27 if (n > 1) result = result / n * (n - 1);
28 return result;
29}
30
31// 旋转群的 Burnside 引理
32// 旋转 k 步的不动点数 = c^gcd(n, k)
33// 优化：按 gcd 值分组，gcd(n,k)=d 的 k 有 φ(n/d) 个
34ll necklace(int n, int c, ll mod) {
35 ll total = 0;
36 // 枚举 n 的因子 d
37 for (int d = 1; (ll)d * d <= n; d++) {
38 if (n % d == 0) {
39 // gcd = d，有 φ(n/d) 个 k
40 total = (total + euler_phi(n / d) % mod * qpow(c, d, mod)) % mod;
41 if (d != n / d) {
42 // gcd = n/d
43 total = (total + euler_phi(d) % mod * qpow(c, n / d, mod)) % mod;
44 }
45 }
46 }
47 // 除以 n（在模意义下用逆元）
48 total = total % mod * qpow(n, mod - 2, mod) % mod;
49 return total;
50}
51
52int main() {
53 int n, c;
54 cin >> n >> c;
55 ll mod = 1e9 + 7;
56 cout << "本质不同的项链数: " << necklace(n, c, mod) << endl;
57 return 0;
58}Burnside 引理：含翻转的手链计数
1#include <iostream>
2using namespace std;
3typedef long long ll;
4
5ll qpow(ll base, ll exp, ll mod) {
6 ll result = 1; base %= mod;
7 while (exp > 0) {
8 if (exp & 1) result = result * base % mod;
9 base = base * base % mod; exp >>= 1;
10 }
11 return result;
12}
13
14ll euler_phi(ll n) {
15 ll result = n;
16 for (ll i = 2; i * i <= n; i++) {
17 if (n % i == 0) {
18 result = result / i * (i - 1);
19 while (n % i == 0) n /= i;
20 }
21 }
22 if (n > 1) result = result / n * (n - 1);
23 return result;
24}
25
26// 二面体群 D_n：包含 n 次旋转 + n 次翻转
27// 翻转部分的不动点：
28// n 为奇数: 每次翻转轴过一个珠子和对边中点，不动点 = c^((n+1)/2)，共 n 种
29// n 为偶数: n/2 种轴过两个珠子（不动点 c^(n/2+1)）+ n/2 种轴过两边中点（不动点 c^(n/2)）
30ll bracelet(int n, int c, ll mod) {
31 // 旋转部分
32 ll rotation_sum = 0;
33 for (int d = 1; (ll)d * d <= n; d++) {
34 if (n % d == 0) {
35 rotation_sum = (rotation_sum + euler_phi(n / d) % mod * qpow(c, d, mod)) % mod;
36 if (d != n / d) {
37 rotation_sum = (rotation_sum + euler_phi(d) % mod * qpow(c, n / d, mod)) % mod;
38 }
39 }
40 }
41
42 // 翻转部分
43 ll flip_sum = 0;
44 if (n % 2 == 1) {
45 // n 种翻转，每种不动点 c^((n+1)/2)
46 flip_sum = (ll)n % mod * qpow(c, (n + 1) / 2, mod) % mod;
47 } else {
48 // n/2 种过顶点：不动点 c^(n/2+1)
49 // n/2 种过边中点：不动点 c^(n/2)
50 flip_sum = ((ll)(n / 2) % mod * qpow(c, n / 2 + 1, mod) % mod +
51 (ll)(n / 2) % mod * qpow(c, n / 2, mod) % mod) % mod;
52 }
53
54 // 总共 2n 个变换
55 ll total = (rotation_sum + flip_sum) % mod;
56 total = total * qpow(2LL * n % mod, mod - 2, mod) % mod;
57 return total;
58}
59
60int main() {
61 int n, c;
62 cin >> n >> c;
63 ll mod = 1e9 + 7;
64 cout << "本质不同的手链数: " << bracelet(n, c, mod) << endl;
65 return 0;
66}✨ 应用示例
示例 1：用 2 种颜色给 4 个珠子的项链着色（只考虑旋转等价）
旋转群 = {旋转 0, 1, 2, 3 步}
| 旋转步数 k | gcd(4, k) | 不动点数 2^gcd |
|---|---|---|
| 0 | 4 | 2⁴ = 16 |
| 1 | 1 | 2¹ = 2 |
| 2 | 2 | 2² = 4 |
| 3 | 1 | 2¹ = 2 |
等价类数 = (16 + 2 + 4 + 2) / 4 = 24 / 4 = 6
这 6 种为：全白、全黑、1白3黑、3白1黑、2白相邻2黑、2白对角2黑。
示例 2：模运算作为等价关系
整数模 3 的等价类：
- [0] =
{..., -6, -3, 0, 3, 6, ...} - [1] =
{..., -5, -2, 1, 4, 7, ...} - [2] =
{..., -4, -1, 2, 5, 8, ...}
三个等价类构成整数集的一个划分。
示例 3：字符串循环同构
字符串集 {"abc", "bca", "cab"} 构成一个等价类（循环同构）。
"abc" 的所有循环移位：abc -> bca -> cab -> abc，形成大小为 3 的等价类。
✨ 解题步骤详解
使用 Burnside 引理：
- 确定集合 X：所有可能的方案（不考虑等价关系）
- 确定群 G：所有使方案等价的变换（旋转、翻转等）
- 对每个 g 属于 G，计算 |X^g|：在变换 g 下不变的方案数
- 求和取平均：等价类数 = Σ|X^g| / |G|
关键技巧：
- 旋转 k 步的不动点：需要每段长度为 gcd(n,k) 的循环节颜色相同
- 翻转的不动点：需要关于对称轴对称的位置颜色相同
- 按 gcd 值分组用欧拉函数优化
✨ 常见错误
- 等价关系三条性质（自反、对称、传递）漏验证一条
- Burnside 引理中忘记除以群的大小 |G|
- 混淆"项链"（只有旋转）和"手链"（旋转+翻转）
- 翻转不动点的计算中，n 的奇偶性分类讨论遗漏
- 在模意义下"除以 |G|"需要用逆元，不能直接整除
- 忘记恒等变换（旋转 0 步）也要计入不动点求和
✨ 总结
| 概念 | 核心要点 |
|---|---|
| 等价关系 | 自反、对称、传递 |
| 等价类 | 互不相交，构成划分 |
| Burnside 引理 | 等价类数 = 不动点数之和 / 群大小 |
| 旋转群 Zₙ | n 次旋转，项链计数 |
| 二面体群 Dₙ | n 次旋转 + n 次翻转，手链计数 |
等价类和 Burnside 引理是处理"本质不同计数"问题的标准工具。在竞赛中，一旦看到"旋转/翻转视为相同"的计数问题，就应该想到 Burnside 引理。掌握不动点的计算技巧是解题的关键。