你好！我是你的OI教练。很高兴看到你对组合数学中这两座“大山”——Burnside引理与Pólya定理产生了兴趣。

很多同学刚接触这两个定理时，会被群论的抽象符号（比如什么“轨道”、“稳定子”）吓倒。但实际上，它们的本质极其朴素，就是为了解决**“包含对称性的计数问题”**。

今天，我们不背干巴巴的公式，我带你拿出一张草稿纸，我们画一画，推一推，让你真正感受到这个定理是怎么“长”出来的。

---

一、 预备知识点扫描（你在登山前需要带的装备）

在推导之前，请确保你的行囊里有以下概念（如果不熟，可以先有个直观印象）：

1. 乘法原理与指数：$m$种颜色涂$n$个格子，无限制有 $m^n$ 种涂法。
2. 置换（Permutation）与置换群：说白了就是“洗牌”或者“变换位置”的规则。比如把第1个放到第2个，第2个放到第3个。所有这些合法变换的集合构成一个“群”（Group，用 $G$ 表示）。
3. 循环（Cycle）分解：任何一种“变换位置”，都可以拆分成几个独立的“圈”。比如 $(1 \to 2 \to 1)$ 是一个长度为2的圈，$(3 \to 3)$ 是一个长度为1的圈。
4. 数论基础（进阶优化用）：最大公约数 $\gcd$ 和 欧拉函数 $\varphi$。

---

二、 启发式推导演练：草稿纸上的奇妙之旅

假设我们正在草稿纸上。我给你一道最基础的思考题：

题目：有一个由3颗珠子串成的手环（圆环），我们有2种颜色（红R，蓝B）可以染。问：如果旋转后长得一样的算同一种，总共有多少种本质不同的手环？

第一步：不考虑对称的“上帝视角”

如果不考虑旋转，把手环剪断拉直，我们有多少种染法？ 在纸上画出来：$2^3 = 8$ 种。

(1) RRR   (2) BBB 
(3) RRB   (4) RBR   (5) BRR
(6) BBR   (7) BRB   (8) RBB

第二步：定义“变换操作”（寻找群 $G$）

对于一个3颗珠子的圆环，我们能做哪些合法的旋转操作？ 在纸上写下我们的3种操作：

• 操作 $g_1$：不转（转0度）。
• 操作 $g_2$：顺时针转1颗珠子（转120度）。
• 操作 $g_3$：顺时针转2颗珠子（转240度）。 这就是我们的置换群 $G$，大小 $|G| = 3$。

第三步：Burnside引理的诞生（算平均不动点）

如果我们手工把旋转后相同的归为一类（一个“等价类”或“轨道”），你会发现：

• RRR 自己是一类（共1种）
• BBB 自己是一类（共1种）
• RRB, RBR, BRR 互相旋转可得，是一类（共1种）
• BBR, BRB, RBB 互相旋转可得，是一类（共1种） 答案是 1+1+1+1 = 4 种。

Burnside引理的脑洞：数学家Burnside不想手工分类。他换了个角度——“算算在每种操作下，有多少个方案是‘岿然不动’的？”

我们在纸上列个表：

1. 用操作 $g_1$（不转）去弄这8个图：显然，8个图全都没变。不动点数 = 8。
2. 用操作 $g_2$（转1格）去弄这8个图：要想转1格后看起来一模一样，必须3颗珠子全是一个颜色！所以只有 RRR 和 BBB 不变。不动点数 = 2。
3. 用操作 $g_3$（转2格）去弄这8个图：同理，只有 RRR 和 BBB 不变。不动点数 = 2。

奇迹出现了：把所有不动点加起来，除以操作的总数：

$$\frac{8 + 2 + 2}{3} = \frac{12}{3} = 4$$

这就是Burnside引理！

公式提取：本质不同方案数 = $\frac{1}{|G|} \sum (操作 g 下的不动点个数)$

第四步：Pólya定理的进化（降维打击）

教练提问：虽然Burnside很帅，但在OI中，如果珠子有100个，颜色有10种，总方案数是 $10^{100}$。你能穷举所有方案去看“谁是不动点”吗？ 你的思考：绝对不行，时间复杂度炸了。我们需要直接算出某个操作 $g$ 下的“不动点个数”。

教练引导：观察刚才的操作 $g_2$（转1格）。珠子1到了位置2，珠子2到了位置3，珠子3到了位置1。这就形成了一个大循环：(1 -> 2 -> 3 -> 1)。 如果一个染色方案在这个操作下是“不动点”，意味着什么？ 你的顿悟：意味着被转移位置的珠子，颜色必须一模一样！也就是同一个循环（圈）里的珠子，必须染同一种颜色！

这就是Pólya定理的核心：

• 假设有 $m$ 种颜色。
• 操作 $g$ 拆分出了 $c(g)$ 个循环。
• 每个循环可以独立选一种颜色，选法是 $m$ 种。
• 所以操作 $g$ 下的不动点个数直接就是：$m^{c(g)}$！

让我们用Pólya复盘刚才的题目（$m=2$）：

1. $g_1$（不转）：珠子各自为政，3个循环 (1)(2)(3)，$c = 3$。不动点 = $2^3 = 8$。
2. $g_2$（转1格）：形成1个大循环 (1->2->3->1)，$c = 1$。不动点 = $2^1 = 2$。
3. $g_3$（转2格）：形成1个大循环 (1->3->2->1)，$c = 1$。不动点 = $2^1 = 2$。 答案：$\frac{1}{3}(2^3 + 2^1 + 2^1) = 4$。 完全一致！但我们再也不需要遍历那8种状态了！

---

三、 复杂度分析与金牌优化建议

1. 空间复杂度： 通常是 $O(N)$，用于存储循环节等信息，非常小。

2. 时间复杂度与优化思路（草稿纸上的演进）：

• 青铜水平（纯Burnside）：$O(|G| \times m^N)$，遍历所有状态。必定超时。
• 白银水平（基础Pólya）：$O(|G| \times N)$。枚举每种置换，然后用 $O(N)$ 找循环节（找连通块）。能过 $N \le 1000$。
• 黄金水平（Pólya + 数论优化）： 当题目是“$N$个珠子的手环旋转”时，$G$ 有 $N$ 个操作（转 $0, 1, \dots, N-1$ 步）。 教练的秘密武器：结论是“转 $k$ 步产生的循环个数为 $\gcd(k, N)$”。 原式变为：$\frac{1}{N} \sum_{k=1}^N m^{\gcd(k, N)}$。 利用欧拉函数 $\varphi$ 将按 $k$ 枚举变为按“$\gcd(k,N)$的值 $d$”枚举（即 $N$ 的约数）： 式子化为：$\frac{1}{N} \sum_{d|N} \varphi(\frac{N}{d}) \times m^d$。 时间复杂度从 $O(N)$ 瞬间降维到 $O(\sqrt{N} \log N)$ （枚举约数 + 求欧拉函数 + 快速幂）。此时 $N$ 开到 $10^9$ 都能秒杀！

---

四、 如何在做题时产生思路（教练的做题提示）

当你面对一道新题时，不要一上来就套公式，按照以下三步走：

1. 明确“对象”与“颜色”：
   • 谁在动？（比如正方体的6个面）
   • 谁在涂？（比如用3种颜色涂面）
2. 找准“置换群 $G$”：
   • 把所有可能让它“长得一样”的变换列出来。如果是正方体，有24种旋转（绕面心转、绕对角线转、绕棱心转等）。一定要做到不重不漏！
3. 终极拷问：用Burnside还是用Pólya？
   • 能用Pólya的前提：颜色是可以任意组合、独立选择的！
   • 必须退回Burnside的情况：如果题目说“相邻珠子不能同色”、“红色珠子最多只能有2个”。此时各个循环块之间的颜色不再独立，$m^{c(g)}$ 就不成立了！
   • 此时的对策：你要回到Burnside引理，用动态规划（DP）或者矩阵快速幂去单独计算每个置换 $g$ 下合法的“不动点个数”。（这是很多高级省选/NOI题目的套路）。

---

五、 划重点：读题时的“题眼”（关键词）

在考场上，当你读到题目包含以下关键词的组合时，你的DNA就应该动了：

• “本质不同” / “算作同一种” —— 这是最强烈的信号。
• “旋转” / “翻转” / “平移” —— 告诉你置换群是什么。
• “手链” / “项链” / “圆桌” / “正多面体” —— 常见的对称载体（注意项链通常可翻转可旋转，而手环/圆桌通常只能旋转，一定要看清题目条件！）。
• “染色” / “分配” / “排列” —— 提示你应用Pólya或者Burnside算不动点。

好了，草稿纸上的推导先到这里。你可以找一道最基础的洛谷模板题（比如 P4980 【模板】Polya定理），按照我们刚才推导的“黄金水平”公式，自己写一下代码。记住，理清“循环节”的规律，这题就破了！有哪里卡住了随时问我。

---

P4980 【模板】Pólya 定理

题目描述

给定一个 $n$ 个点，$n$ 条边的环，有 $n$ 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 $10^9+7$ 取模。

注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。

输入格式

第一行输入一个 $t$，表示有 $t$ 组数据

第二行开始，一共 $t$ 行，每行一个整数 $n$，意思如题所示。

输出格式

共 $t$ 行，每行一个数字，表示染色方案数对 $10^9+7$ 取模后的结果

输入输出样例 #1

输入 #1

5
1 
2 
3 
4 
5 

输出 #1

1
3
11
70
629

说明/提示

$$n \leq 10^9$$ $$t \leq 10^3$$