基础
群
给定一个集合 \(G\) 和集合上的二元运算 \(\times\)，满足：
- 封闭性，若 \(a,b\in G\)，则 \(a\times b\in G\)。
- 结合律，对于任意 \(a,b,c\in G\)，则 \((a\times b)\times c=a\times (b\times c)\)。
- 存在单位元，\(e[x]=x\)。
- 存在逆元。
则称 \(G\) 在运算 \(\times\) 下是一个群。
子群
定义群 \((G,\times)\), \((H,\times)\)，满足 \(H\subseteq G\)，则 \((H,\times)\) 是 \((G,\times)\) 的子群。
陪集
若 \(G\) 为群，\(H\) 为其子群，而 \(g\) 为 \(G\) 中元素，则：
\(gH = \{gh : h\in H\}\) 为H在G中的左陪集。
\(Hg = \{hg : h\in H\}\) 为H在G中的右陪集。
例如一个示例：
加法循环群 \(Z_4 = \{0, 1, 2, 3\} = G\)，有子群 \(H = \{0, 2\}\)。\(H\) 在 \(G\) 中的左陪集为：
\[\begin{align} 0 + H &= \{0, 2\} = H\\ 1 + H &= \{1, 3\}\\ 2 + H &= \{2, 0\} = H\\ 3 + H &= \{3, 1\}\\ \end{align} \]因此存在两种不同的陪集 \(H\) 本身和 \(1 + H = 3 + H\)。
注意每个 \(G\) 中元素要么在 \(H\) 中，要么在 \(1 + H\) 中。
即，\(H ∪ (1 + H ) = G\)，所以 \(H\) 在 \(G\) 中不同的陪集构成 \(G\) 的一个划分。
所以陪集存在以下性质：
- 对于一个子群 \(H\) 的两个左（右）陪集要么相同，要么不交。
- 左（右）陪集的集合构成了群 \(G\) 的一个划分，这个划分称为 \(G\) 对 \(H\) 的左（右）陪集分解。
- 群中的每个元素属于且仅属于一个左（右）陪集。
- 特别地，单位元只在一个陪集中，即是 \(H\) 自己。
- \(H\) 是所有左（右）陪集中唯一的子群。
- \(H\) 的所有左（右）陪集的阶都是一样的。
- \(H\) 在 \(G\) 中的左陪集个数和右陪集个数相同。
- \(gH=H\)，当且仅当 \(g\in H\)。
我们定义 \(H\) 在 \(G\) 中的左陪集个数和右陪集个数为 \(H\) 在 \(G\) 中的指数，记作 \([G:H]\)。
拉格朗日定理
\[|G|=[G:H]\times |H| \]由陪集的性质很容易理解。
轨道
我们定义 \(\forall x,y\in X,x\sim y\) 当且仅当 \(\exists g\in G,\ s.t.\ g[x]=y\)。
存在以下性质：
- 自反性，因为存在 \(e[x]=x\)。
- 对称性，若 \(g[x]=y\)，由于 \(g\) 存在逆元，得 \(g^{-1}[g[x]]=(g^{-1}\times g)[x]=x=g^{-1}[y]\)。
- 传递性，若 \(g_1[x]=y,g_2[y]=z\) ，则 \((g_2\times g_1)[x]=g_2[y]=z\).
定义 \(O_x\) 为元素 \(x\) 所在的由关系 \(\sim\) 导出的等价类，称为 \(x\) 所在的轨道。
显然 \(x\) 所在的轨道的含义是：所有与 \(x\) 可以经过某个群中元素作用而相互得到的元素所组成的集合。
这里需要注意的是： \(O_x\subset X\) ，轨道是被作用集合的子集。
由于 \(O_x\) 本质上是等价关系所诱导出的等价类，其还具有所有等价类所具有的优良性质，其具有以下性质：
- \(\forall x,y\in X,x\sim y\) 当且仅当 \(O_x=O_y\)。
- 任意两个轨道要么相同要么不交。
- 所有不同轨道给出了集合 \(X\) 的一个划分，即在 \(X\) 每条不同轨道上选取一个元素组成集合 \(I\) 的话，有 \(X=\bigcup_{x\in I}O_x\)。
\(O_x\) 是关于群作用下对于集合 \(X\) 中元素进行分类的结果。
但事实上，群作用不仅仅对 \(X\) 中元素有分类作用，对于 \(G\) 中元素同样具有分类作用。
稳定化子
定义对于 \(x\in X\) ，\(G_x=\left \{ g\in G|g[x]=x \right \}\) 被称为群作用下元素 \(x\) 的稳定化子。
这个定义的含义是 对于 \(G_x\subset G\)，其中元素对于 \(x\) 均有不变作用。
容易发现：
\(\forall g_1,g_2\in G_x,g_1g_2^{-1}[x]=g_1[x]=x\)，所以 \(g_1g_2^{-1}\in G_x\)。
依据子群判定定理，稳定化子必定是作用群 \(G\) 的子群。
这样由群中元素关于陪集的划分，我们就可以很自然地基于稳定化子给出关于群 \(G\) 的划分。
轨道稳定化子定理
\[|O_x|=\frac{|G|}{|G_x|}=[G:G_X] \]即 \(x\) 所在轨道元素个数等于 \(x\) 的稳定化子的不同陪集数。
Burnside 引理
引理
我们可以令 \(X^g\) 表示 \(X\) 中在 \(g\) 作用下的不动元素，并将轨道数记作 \(|X/G|\)，则：
\[|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g| \]从而轨道数等于被 \(G\) 中一个元素保持不动的点个数的平均值。
证明
Burnside 引理基于如下观察：
如果我们将 \(g_i\in G,x_i\in X\) 写成有序对形式，我们可以得到一个矩阵 \(A\)，其中 \(A_{i,j}=(g_i,x_j)\)，则 \(A\) 为 \(|G|\times|X|\) 大小的矩阵。
我们先考虑每一列，每一列的 \(x_j\) 值都相同，我们对于不同 \(g_i\) 进行计数，显然有 \(|G_{x_j}|\) 个元素不变。
我们在考虑每一行，此时 \(g_i\) 不变，我们对于不同的 \(x_j\) 计数，则有 \(|X^{g_i}|\) 个元素不变。
而一个有序对 \((g_i,x_j)\) 对于 \(|G_{x_j}|\) 有贡献当且仅当 \(g_i[x_j]=x_j\) 当且仅当 \(x_j\in X^{g_i}\)。
故我们可以得到：
\[\sum_{g\in G}|X^{g_i}|=\sum_{x\in X}|G_x| \]可以继续拓展这个结论：
\[\sum_{g\in G}|X^{g}|=\sum_{x\in X}|G_x| \]由于 \(|G_x|=\frac{|G|}{|O_x|}\)，得到：
\[\sum_{g\in G}|X^{g}|=\sum_{x\in X}\frac{|G|}{|O_x|}=|G|\sum_{x\in X} \frac{1}{|O_x|} \]我们利用轨道的性质，\(X\) 可以写作不同轨道的划分，不妨设 \(X=O_1\cup...\cup O_{|X/G|}\)。
故 \(\sum_{x\in X} \frac{1}{|O_x|}=|X/G|\) 即不同轨道的数量。
故 \(\frac{1}{|G|}\sum_{g\in G}|X^{g}|\) 即为不同轨道的数量，与上文式子相同。
Polya 定理
定理
我们令 \(N\) 为颜色集合。
\[|X/G|=\frac{1}{|G|}\sum_{g\in G}|N|^{c(g)} \]证明
我们只需要说明 \(|N|^{c(g)}=|X^g|\)。
发现每个轮换等价于一个连通块，那么 \(X^g\) 中必然是每个轮换染相同的颜色即可。
每个轮换自然有 \(∣N∣\) 种方案，也就是 \(|N|^{c(g)}\)。
例题
例一
题面
https://www.luogu.com.cn/problem/P4980。
\(t\) 组数据，给定一个 \(n\) 个点，\(n\) 条边的环，有 \(n\) 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 \(10^9+7\) 取模。
注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。
\(n\le 10^9,t\le 10^3\)。
思路
我们发现旋转 \(k\) 次，它共有 \(\gcd(n,k)\) 个轮换。
则答案为：
\[\begin{align} &=\sum_{i=1}^n n^{\gcd(n,i)}\\ &=\sum_{k=1}^nn^k\sum_{i=1}^n [\gcd(n,i)=k]\\ &=\sum_{k|n}^nn^k\sum_{i=1}^{\frac{n}{k}} [\gcd(n,i)=1]\\ &=\sum_{k|n}^nn^k\varphi(\frac{n}{k}) \end{align} \]暴力计算即可。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
inline int power(int x, int y) {
int res = 1;
while (y) { if (y & 1) res = res * x % mod; x = x * x % mod, y >>= 1; }
return res;
}
inline int phi(int x) {
int res = x;
for (int i = 2; i <= sqrt(x); i++) {
if (x % i == 0) res = res - res / i;
while (x % i == 0) x /= i;
}
return (x == 1 ? res : res - res / x);
}
inline void add(int&x, int y) { if ((x += y) >= mod) x -= mod; }
signed main() {
int t; cin >> t;
while (t--) {
int n;
cin >> n;
int m = sqrt(n), ans = 0;
for (int i = 1; i <= m; i++)
if (n % i == 0) {
ans = (ans + power(n, n / i) * phi(i)) % mod;
if (i * i != n) ans = (ans + power(n, i) * phi(n / i)) % mod;
}
cout << ans * power(n, mod - 2) % mod << endl;
}
return 0;
}
例二
题面
https://www.luogu.com.cn/problem/P1446。
小春现在很清闲，面对书桌上的 \(n\) 张牌，他决定给每张牌染色，目前小春拥有 \(3\) 种颜色：红色，蓝色，绿色。他询问 Sun 有多少种染色方案，Sun 很快就给出了答案。
进一步，小春要求染出 \(S_r\) 张红色，\(S_b\) 张蓝色，\(S_g\) 张绿色。他又询问有多少种方案，Sun 想了一下，又给出了正确答案。最后小春发明了 \(m\) 种不同的洗牌法，这里他又问 Sun 有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法（即可以使用多种洗牌法，而每种方法可以使用多次）洗成另一种。
Sun 发现这个问题有点难度，决定交给你，由于答案可能很大，你只需要求出答案对于 \(P\) 取模的结果。 保证 \(P\) 为一个质数。
\(S_r,S_b,S_g\le 20,m\le 60\)，保证洗牌构成群。
思路
Burnside 引理模板题。
由于颜色数有限制，不好用 polya，所以可以考虑 Burnside。
如何求不动点个数。
我们将每一个置换的轮换找出来。
那么每一个轮换内部都需要是同一种颜色。
可以设 \(f_{i,j,k,l}\)，表示到第 \(i\) 个轮换，还要染 \(j\) 个红色，\(k\) 个蓝色，\(l\) 个绿色。
直接暴力转移即可。
时间复杂度：\(O(nmS_rS_bS_g)\)。
Code
#include <bits/stdc++.h>
using namespace std;
int sr, sb, sg, m, n, p, ans;
int v[65];
int a[65][65];
int f[65][25][25][25];
inline void add(int&x, int y) { if ((x += y) >= p) x -= p; }
int main() {
cin >> sr >> sb >> sg >> m >> p, n = sr + sb + sg;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) cin >> a[i][j];
++m;
for (int i = 1; i <= n; i++) a[m][i] = 1;
for (int i = 1; i <= m; i++) {
memset(f, 0, sizeof f);
memset(v, 0, sizeof v);
int las = 0;
f[0][sr][sb][sg] = 1;
for (int j = 1; j <= n; j++) {
if (v[j]) continue;
int ct = 0;
for (int k = j; !v[k]; k = a[i][k]) v[k] = 1, ct++;
for (int u = 0; u <= sr; u++)
for (int v = 0; v <= sb; v++)
for (int w = 0; w <= sg; w++) {
if (f[las][u][v][w] == 0) continue;
if (u >= ct) add(f[j][u - ct][v][w], f[las][u][v][w]);
if (v >= ct) add(f[j][u][v - ct][w], f[las][u][v][w]);
if (w >= ct) add(f[j][u][v][w - ct], f[las][u][v][w]);
}
las = j;
}
add(ans, f[las][0][0][0]);
}
while (ans % m != 0) ans += p;
cout << (ans / m) % p << "\n";
}
例三
题面
https://www.luogu.com.cn/problem/AT_arc062_d。
给定一张 \(N\) 个点 \(M\) 条边的无向图，每条边要染一个编号在 \(1\) 到 \(K\) 的颜色。
你可以对一张染色了的图进行若干次操作，每次操作形如，在图中选择一个简单环（即不经过相同点的环），并且将其颜色逆（顺）时针旋转一个单位。
两种染色方案被认为是本质相同的，当且仅当其中一种染色后的图经过若干次操作后可以变成另一种染色后的图。
问有多少本质不同的染色方案，输出对 \(10^9+7\) 取模。
\(N\le 50,M\le 100,K\le 100\)。
思路
对于一个点双，我们可以发现：
- 假如它是一个简单环，那么它只能旋转这一个环，我们可以使用 polya 定理计算。
- 假如它是多个环的组成，那么它的颜色可以随意调动，任何的情况都可以得到，那么假如说有 \(m\) 条边，方案数则为 \(\binom{m+k-1}{k-1}\)，我们只考虑每一种颜色的出现次数。
对于其他的边，都可以随意染色。
那么我们直接提出所有点双，统计方案即可。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int n, m, k, tp, tt, ct, ans = 1;
int p[210], dn[210], lw[210], st[210], vs[210];
int c[210][210];
vector<int> to[210];
vector<int> ot[210];
inline void tarjan(int x, int fa) {
dn[x] = lw[x] = ++tt, st[++tp] = x;
for (auto i : to[x]) if (i != fa) {
if (!dn[i]) {
tarjan(i, x);
lw[x] = min(lw[x], lw[i]);
if (lw[i] >= dn[x]) {
ot[++ct].push_back(x);
while (ot[ct].back() != i) ot[ct].push_back(st[tp--]);
}
} else lw[x] = min(lw[x], dn[i]);
}
}
inline int sol(int x) {
int r = 0;
for (int i = 1; i <= x; i++) r = (r + p[__gcd(i, x)]) % mod;
while (r % x != 0) r += mod;
return r / x % mod;
}
signed main() {
for (int i = 0; i <= 200; i++) c[i][0] = 1;
for (int i = 1; i <= 200; i++)
for (int j = 1; j <= i; j++)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
cin >> n >> m >> k;
p[0] = 1;
for (int i = 1; i <= m; i++) p[i] = p[i - 1] * k % mod;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
to[u].push_back(v);
to[v].push_back(u);
}
for (int i = 1; i <= n; i++) if (!dn[i]) tarjan(i, 0);
for (int i = 1; i <= ct; i++) {
int ps = 0;
for (auto j : ot[i]) vs[j] = 1;
for (auto j : ot[i]) for (auto k : to[j]) ps += vs[k];
for (auto j : ot[i]) vs[j] = 0;
ps = ps / 2;
if (ps == ot[i].size()) ans = ans * sol(ps) % mod;
else if (ps < ot[i].size()) ans = ans * p[ps] % mod;
else if (ps > ot[i].size()) ans = ans * c[ps + k - 1][k - 1] % mod;
}
cout << ans << "\n";
}