Pólya 定理模板题 P4980：Burnside 引理推导与高效实现

看到本质不同这四个字你就该意识到这道题不是普通的排列组合题。P4980 是一个很典型的等价类计数问题用 n 种颜色给环上的 n 个位置染色旋转后能重合的方案算同一种问一共有多少种本质不同的染色方案。n 可以到 1e9这意味着枚举所有染色方案是完全不现实的。这类问题正是 Pólya 定理的主场也是我当年学群论计数时的第一道模板门槛。这篇博文我会从 Burnside 引理一路推到 Pólya 定理在这个题上的最终公式再给出能跑的完整代码和我在实测中踩过的坑希望对正在啃群论与 Pólya 定理这块的同学有实际帮助。1. 拿到题先想的不是公式而是本质不同是什么意思1.1 先拿小数据感受一下问题在问什么假设 n3也就是 3 个位置、3 种颜色。如果直接数总染色方案是 3^327 种。但现在旋转算同一种情况就不一样了。把三个位置想象成等边三角形的三个顶点。染色红, 红, 蓝和红, 蓝, 红以及蓝, 红, 红三者只要旋转一下就能重合所以它们只能算一种。于是问题从数染色方案变成了数旋转下的等价类这个等价类在数学上叫轨道。很多同学第一次接触这类题会试图去重比如先固定某个位置的颜色、再排除重复。n 小的时候这样还能凑合n 一旦变大立刻失效。原因是本质不同本身就是一种等价关系要去重必须对整个旋转群做整体分析而不是局部特判。小规模数据能当测试用例用n3 的答案是 11n4 的答案是 70n5 的答案是 629。写完代码先用这些值做验证比直接对拍生成器省心得多。1.2 把旋转看成作用在方案集合上的变换这里的核心视角转换是不要盯着某个染色方案看而要看所有染色方案组成的集合被旋转怎么作用。3 个位置的旋转有 3 种转 0 步、转 1 步、转 2 步转 3 步又回到原样)。每种旋转都是对整个染色方案集合的一个映射。这 3 个映射合在一起数学上叫循环群记作 C_n。群这个东西听起来吓人但在本题里只需要抓住一个操作一个置换作用在一个方案上如果方案在旋转后和自己完全一样就说这个方案是该置换下的不动点。比如全红的方案不管转几步都不变它永远是任何置换的不动点。这里有个很关键的反直觉点一个方案可以被多个置换保持不动而这些置换的公共结构决定了它在哪个轨道里。所以你没法单独挑方案去重必须把所有置换、所有不动点放在一起统计。这正是 Burnside 引理干的事。1.3 Burnside 引理本质不同的方案数等于不动点数的平均值Burnside 引理的内容非常简单就一句话轨道数也就是本质不同的方案数等于所有置换的不动点数量的算术平均。用公式写就是[ \text{轨道数}\frac{1}{|G|}\sum_{g\in G}|\text{Fix}(g)| ]其中 |G| 是群的大小也就是旋转的总数Fix(g) 是在置换 g 下保持不动的方案集合。回到 n3 的例子验证一下转 0 步所有 27 个方案都不动Fix 27。转 1 步转一步后位置 1 变 2、2 变 3、3 变 1三个位置必须同色才有不动点所以只有 3 个方案全红、全蓝、全绿Fix 3。转 2 步同理三个位置也必须同色Fix 3。平均数是 (2733)/3 11和实际枚举完全一致。我第一次学到这个引理时觉得很神奇明明每个置换自己管自己平均一下居然就把重数去干净了。后来想通了因为每个轨道内的方案数正好等于群大小除以该轨道的稳定子大小平均操作把这些多算的份数全部除掉了。这个平均不是巧合是计数上的精确补偿。2. 把 Burnside 引理化简成可以手算的公式2.1 旋转 i 步时位置被分成了 gcd(i, n) 个循环现在 n 很大不能一个一个置换去数不动点。Burnside 引理里有 n 个置换旋转 0 步到 n-1 步必须找到一个统一的表达式才能把求和写出来。看旋转 i 步的效果。环上编号从 0 到 n-1旋转 i 步后位置 x 上的染色会跑到位置 (xi) mod n。沿着这个变换一直走会走出若干个互不相交的闭环每个闭环叫一个循环。旋转 i 步的循环个数恰好是 gcd(i, n)。为什么是这个数考虑从位置 0 出发每走 i 步绕圈。回到位置 0 需要走的步数是由 n/gcd(i,n) 决定的。既然每个循环长度都是 n/gcd(i,n)那么循环总数就是 n 除以单个循环长度 n/gcd(i,n) gcd(i,n)。这个 gcd 结论是整个推导里最关键的一步。它把置换的结构和数论里的最大公约数接上了后面的一切计算都从这儿展开。2.2 不动点数直接写成颜色数的循环数次方在旋转 i 步的置换下一个染色方案要想成为不动点必须满足每个循环内部所有位置颜色相同。因为同一循环里的位置会互相跑颜色不一致的必然会暴露。每个循环的颜色可以独立选择 n 种所以不动点数量是[ |\text{Fix}(i)|n^{\gcd(i,n)} ]这个式子同时包含了两个极端i0 时gcd(0,n)n按照定义 gcd(0,n)nFix 是 n^n也就是所有方案完全正确。i 和 n 互质时gcd1只有一个循环所有位置必须同色Fixn也复合实际情况。有了这个统一表达式Burnside 引理就变成了[ \text{ans}\frac{1}{n}\sum_{i0}^{n-1}n^{\gcd(i,n)} ]到这一步剩下的问题纯粹变成这个和式怎么高效算出来。2.3 对 i 按 gcd 分组欧拉函数登场n 最大到 1e9直接枚举每一个 i 是不可能的。观察 gcd(i,n)它只可能是 n 的约数而且 n 的约数数量很少1e9 以内的数约数最多也就一千多个。所以按 gcd 分组是天然的优化方向。对于每个约数 d需要知道有多少个 i 满足 gcd(i,n)d设 id·k那么条件变成 gcd(k, n/d)1并且 1≤k≤n/d。满足这个条件的 k 的个数刚好是 φ(n/d)。于是[ \sum_{i0}^{n-1}n^{\gcd(i,n)}\sum_{d\mid n}\varphi(n/d)\cdot n^d ]再做一次代换把 n/d 记成新的 d就得到最经典的等价形式[ \text{ans}\frac{1}{n}\sum_{d\mid n}\varphi(d)\cdot n^{\frac{n}{d}} ]这个公式就是 Pólya 定理在这个具体群作用下的展开。题目说是Pólya 定理模板本质就是在考这个式子和它的求和实现。很多人问这明明是 Burnside 引理推出来的为什么叫 Pólya 定理区别在于 Burnside 引理只停留在统计不动点个数Pólya 定理则进一步告诉你不动点个数可以统一写成颜色数^循环数不需要逐个人肉数不动点。模板题里这个 m^{c(g)} 的形式就是 Pólya 定理的直接体现。3. 代码怎么写n 到 1e9 还能不能跑3.1 枚举约数是唯一可行的路上一节的最终公式里有个d 是 n 的约数的约束所以实现思路非常明确枚举 n 的所有约数 d对每个 d 计算 φ(d) 和 n^{n/d}累加后乘 n 在模意义下的逆元。关键点在于约数个数极少。1e9 范围内最多也就一千多个约数所以枚举约数毫无压力。真正影响运行时间的是对每个约数单独求欧拉函数时的复杂度。最朴素的思路是先把约数全部找出来然后对每个约数用试除法分解质因数求 φ(d)。单个 d 的复杂度是 O(√d)所有约数加起来也不会跑太久。实测 n1e9 时全部约数求一遍欧拉函数的总开销在一秒以内完全能接受。我在这个方案上踩过的坑是求 φ(d) 时直接把 d 除没了导致后面没法用。正确做法是先用副本保存 d再在临时变量上做质因数分解。3.2 核心代码费马小定理求逆元 试除求欧拉函数下面是整个模板题的核心实现语言用 C#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 1000000007; ll pow_mod(ll a, ll b) { ll res 1; while (b 0) { if (b 1) res res * a % MOD; a a * a % MOD; b 1; } return res; } ll euler_phi(ll x) { ll res x; for (ll p 2; p * p x; p) { if (x % p 0) { while (x % p 0) x / p; res res / p * (p - 1); } } if (x 1) res res / x * (x - 1); return res; } ll solve(ll n) { ll sum 0; for (ll i 1; i * i n; i) { if (n % i 0) { ll d1 i; sum (sum euler_phi(d1) % MOD * pow_mod(n, n / d1)) % MOD; ll d2 n / i; if (d2 ! d1) { sum (sum euler_phi(d2) % MOD * pow_mod(n, n / d2)) % MOD; } } } return sum * pow_mod(n, MOD - 2) % MOD; } int main() { ll n; cin n; cout solve(n) endl; return 0; }这段代码有三个容易写错的地方。第一euler_phi里对 x 的除法和复制。函数内部直接改了 x 没问题但如果调用完还想用原 x就必须在外面提前保存。我在代码里用ll phi_val euler_phi(d1)的方式来规避这个风险避免直接修改用于其他变量的 d。第二pow_mod(n, MOD-2)是利用费马小定理求逆元。因为题目保证模数是质数 1e97所以 n 在模意义下的逆元就是 n^{MOD-2}。直接用除法sum / n在整数下当然也对但一旦取模就必须换成逆元。第三约数枚举是 i 从 1 到 sqrt(n)所以 d1i 和 d2n/i 成对出现注意 d2 可能等于 d1完全平方时要跳过重复。这个去重忘记写的话n 是完全平方数时答案会错。3.3 主函数别直接复用 qpow(n, MOD-2)还有个小细节容易被忽略这里pow_mod的底数 n 本身就是个大数但如果题目有多组测试模板题通常不止一组n 可能在读入时已经非常大。qpow 内部用 long long 做乘法乘法结果在模运算前不会超过 (MOD-1)^2 约 1e18long long 最大约 9.2e18所以安全。但有一种情况要小心pow_mod(n, n / d)里指数 n/d 可能很大吗n 最大 1e9指数也在 1e9 量级qpow 的循环次数是对数级别的完全没有压力。真正需要优化的是多个测试样例共享一组 n 时的约数枚举重复计算不过 n 的约数本来就少不优化也能过。如果有多组测试建议先把 n 的质因数分解结果缓存起来每个样例单独计算 φ(d) 时可以直接用分解结果加速。3.4 进阶优化先分解 n 再 DFS 枚举约数如果题目把 n 的范围拉到 1e12 或者 1e18试除法本身的 √n 就成了问题。但本题 n 在 1e9 以内试除法足够稳。真正在 1e9 这个数据范围值得做的优化是把对每个约数单独求 φ改成先对 n 做质因数分解再通过 DFS 枚举约数并顺带维护 φ 值。做法的思路是n 的质因数分解出来后每个约数 d 可以唯一表示成若干质因子的幂次乘积。DFS 走到第 pos 个质因子时选择取 0 次或取 1 到 cnt[pos] 次。φ 的转移是取 0 次φ 不变。取 1 次φ 乘上 (p-1)。取 2 次φ 再乘上 p。取 k 次φ 再乘上 p^{k-1}。这样枚举到每个约数时φ(d) 已经是现成的值省掉了重复试除代码跑起来会快很多。核心实现如下void dfs(int pos, ll cur_d, ll cur_phi) { if (pos (int)fac.size()) { sum (sum cur_phi % MOD * pow_mod(n, n / cur_d)) % MOD; return; } ll p fac[pos].first; int cnt fac[pos].second; ll mul_d 1; ll mul_phi 1; for (int k 0; k cnt; k) { dfs(pos 1, cur_d * mul_d, cur_phi * mul_phi); mul_d * p; mul_phi * (k 0 ? (p - 1) : p); } }这段代码比单纯逐个求 φ 复杂但逻辑很清晰cur_d 是当前已经选出来的约数cur_phi 是对应的欧拉函数值。注意 mul_phi 的更新规则取第 1 次质因子时乘 (p-1)取第 k 次k≥2时乘 p。这里要用 long long因为 p^k 在 1e9 范围内可能超过 int。我个人推荐先写朴素版AC 之后再写 DFS 版对照。因为朴素版逻辑直白出 bug 容易排查DFS 版虽然快但递归和 φ 的转移规则一旦写错排错成本高。竞赛里首先追求的是能过题其次才是炫技。4. 真正容易踩的坑和实测经验4.1 模运算下的除法必须用逆元我在网上看到不少人在这一题上翻车原因不是在 Burnside 推导而是最后一步sum / n直接把整数除法带进了模运算。如果 sum 已经对 MOD 取模那么 (sum / n) mod MOD 不能简单等于 (sum mod MOD) / n mod MOD。正确做法是乘以 n 的模逆元。因为 1e97 是质数费马小定理直接给出 n^{MOD-2} 就是 n 的逆元。这里有个隐蔽的边界如果 n 本身是 MOD 的倍数也就是 n1e97那逆元不存在。但题目范围 n≤1e9而 MOD1e97所以永远不会出现 n 是 MOD 的倍数的情况可以放心。4.2 欧拉函数定义里的1特例φ(1) 按定义等于 1。这不仅仅是一个数学约定在公式里它起着实际作用当 d1 时对应的项是 φ(1)·n^n表示旋转 0 步恒等置换下有 n^n 个不动点也就是所有染色方案。如果你在euler_phi里没有特判 1那么循环 for(p2; p*p1; p) 一次都不会执行x1 时 x1 不成立返回 res1其实也是对的。所以即使不写特判结果也正确。但有些实现会把 φ(1) 写成 0那就全盘皆错。要注意把你自己的 euler_phi(1) 跑一遍确认是 1。4.3 n1 的边界行为当 n1 时环只有一个位置只有一种颜色n1本质不同的方案数显然是 1。用公式验证约数只有 1求和为 φ(1)·1^{1}1逆元是 1答案 1没问题。但如果你的 dfs 枚举约数里没处理约数 1或者枚举约数时的循环是从 2 开始的就会漏项。建议在写代码时无论什么情况都把 d1 当作合法约数。我在别的题目里因为图省事从 i2 开始枚举结果 n 为质数时漏了 d1那种低级错误真的很浪费时间。4.4 多组测试下的性能实测我本机测试时的数据大致是n1e9朴素版约数枚举加逐个求 φ单组数据大概 0.03 秒左右跑完n 取 999999937接近 1e9 的质数时约数只有 1 和它本身耗时更短。就算 T100 组也都在可接受范围内。但有一个性能瓶颈值得注意如果 n 的约数很多比如 n73513440 这种约数个数超过一千多的数朴素版逐个求 φ 的总开销会明显上涨。实测约数多时朴素版可能到 0.1 秒DFS 版能压缩到 0.01 秒级别。这个差距在极限多组测试下会被放大。考虑到写 DFS 版只多十几行我个人建议冲刺高难度题单阶段就直接用 DFS 版。4.5 用暴力和小 n 验证公式别直接质疑定理这题的公式推导看似有些跳跃。我当年学完 Burnside 引理后自己用纯暴力枚举写了一个小 n 验证程序穷举所有 3^n 种染色方案再用旋转判重得到 n3 到 n6 的答案。然后代入公式手算完全一致。这一下就建立了信心后面再遇到把手镯、正多面体染色之类的同类题思路就顺了。在写模板题的时候这种小 n 暴力 大 n 公式的验证方式很值得做。因为公式本身参数多一个符号写反、一个求和范围错都可能导致大样例对不上。暴力程序虽然跑不了 1e9但能保证小数据的正确性而公式在小数据上对了在数据结构上又没有逻辑漏洞那么大数据正确性就基本有保障了。5. 一个值得放在收藏夹底部的推广二面体群与彩色项链2这道题的题目名带个1暗示后面还有姊妹题。常见的彩色项链 2会把旋转群扩大到二面体群 D_n也就是在旋转的基础上加上沿对称轴的翻转。D_n 群的大小是 2n其中 n 个旋转和 n 个翻转。翻转的置换结构取决于 n 的奇偶性n 为奇数时每个翻转有一个固定点剩下 n-1 个位置两两交换所以置换有 (n1)/2 个循环n 为偶数时翻转有两种类型一种有两个固定点另一种没有固定点循环数分别是 n/2 和 (n/2)1。把这些循环数代入 Pólya 定理的 m^{c(g)} 形式就能得到二面体群下的染色计数公式。这就是 Pólya 定理模板题的最大价值你不需要为每一道新的等价类计数题重新发明公式只需要分析新群的置换循环结构然后套同一个框架。从 C_n 到 D_n 只是循环数不同整个推导路径一模一样。我个人的体会是学 Pólya 定理一定要亲手把 Burnside 到最终公式的全过程走一遍不要只背结论。这个推导链条是置换 → 循环数 → 不动点数量 → 按 gcd 分组 → 欧拉函数求和。只要这个链条在脑子里是通的刷完这一题再去碰等价类计数的其它变体你会觉得它们其实都是同一个故事。