如果给你9颗珠子红、蓝、黄各3颗让你串一条手链你觉得最后能得到多少种真正不同的样式我第一次认真算这道题时随口猜了个大概几百上千结果程序跑出来是个很不起眼的94。这个答案让我愣了很久因为直觉上9颗珠子能摆出的线性排列明明有1680种怎么一上手链就缩水成两位数了。后来把旋转和翻转的对称性逐项算清楚才明白这道手链样式组合数学题藏得有多深。这篇就把完整的拆题、暴力验证、理论计算和踩坑过程都写出来给准备算法竞赛、或者想彻底搞懂Polya计数的朋友参考。1. 手链样式这道题题面里到底藏着什么1.1 把题面翻译成数学模型题目表面上是手工问题三种颜色各3颗珠子穿成环形手链问有多少种不同样式。但一旦要精确计算就得先回答一个关键问题——“不同样式”到底怎么定义数学上的定义是两条手链如果能通过旋转或者翻转变成同一条就视为同一种样式。这里有两个隐藏约束值得细说。第一珠子只有颜色区别没有编号所以“红1、红2、红3”互换位置不算新样式。第二手链是环形且可翻面的这与“项链”有微妙区别。不少题目会把项链定义成只能旋转、不能翻转手链则允许翻面。手链样式的计数结果94就是同时把旋转和翻转都算作同构得到的。如果给9个位置编号不考虑对称性只安排颜色排列数是9的阶乘除以三个3的阶乘也就是1680。这1680个带编号排列是后面所有计算的出发点。手链样式问题本质上就是研究这1680个排列在“旋转”和“翻转”操作之下会合并成多少个等价类。1.2 为什么“样式相同”是一个等价关系“旋转后相同”“翻转后相同”听起来很直观但值得从数学上确认一下它确实是等价关系因为后面用群论计算时靠的就是这条性质。假设定义两个线性排列等价当且仅当其中一个能经过若干次旋转、翻转变成另一个。那么自反性显然成立任何排列旋转0度等于自己对称性也成立因为每次旋转、翻转都有逆操作传递性同样成立两次操作的复合还是旋转或翻转操作。满足这三条就能把1680个排列划分成互不相交的等价类每个等价类对应一种手链样式。这一步很多初学者会忽略直接拿枚举结果除以18旋转9种乘翻转2种想当然去算最后得到93.33这种非整数就发现不对劲了。原因就在于部分排列有特殊的对称性导致它们的等价类大小并不是统一的18。后面用Burnside引理处理的就是这种不均等。2. 不想数学推导那就先把暴力搜索跑起来2.1 生成1680个线性排列竞赛里遇到拿不准的计数题我习惯先写一个暴力程序把答案跑出来哪怕慢一点也无所谓。这道题数据规模很小9颗珠子就算全排列也只有36万种计算机完全扛得住。第一步是生成所有颜色不同的线性排列。直接对字符串RRRBBBYYY做全排列再用集合去重就能得到1680个有效排列。代码如下from itertools import permutations base RRRBBBYYY unique_perms set(permutations(base)) print(len(unique_perms)) # 输出 1680这里有个细节permutations(base)本身会产生362880个结果因为我用了可迭代对象而不是原始字符串列表所以包含大量因为相同颜色珠子互换而完全相同的排列。用set去重后才得到真正的1680个颜色组合。2.2 用最小表示法去重拿到1680个线性排列后第二步是对每个排列生成它的全部等价表示再统一去重。旋转操作容易实现把字符串首尾相接依次从每个位置截取长度为9的子串就能得到9种旋转结果。翻转操作对环形链来说等价于把线性排列倒序后再旋转所以把字符串反转之后再同样取9种旋转结果即可。把所有可能的18种表示放进一个列表取字典序最小的那个作为这个等价类的“代表”最后统计代表的总数即可。完整代码如下def normalize(s: str) - str: n len(s) doubled s s candidates [doubled[i:in] for i in range(n)] rev s[::-1] rev_doubled rev rev candidates [rev_doubled[i:in] for i in range(n)] return min(candidates) styles set() for p in unique_perms: styles.add(normalize(.join(p))) print(len(styles)) # 输出 94这段代码的思路可以扩展到任意环形去重场景。最小表示法不要求真的“旋转珠子”只需要保证同一个等价类无论从哪个表示进入最后都输出同一个字符串。这里用字典序min作为规范化函数简单可靠。2.3 先跑一个能让自己信服的答案暴力跑出94之后最好再验证一下这个结果没有手滑。方法是用另一种方式统计等价类大小之和遍历1680个排列每遇到一个未标记的排列就把它的18种表示全部标出来数一数它所在等价类实际有多大。把各个等价类的大小加起来应该重新得到1680。我实测下来的分布很有规律其中一个等价类比较特殊只包含6个排列其余93个等价类每个包含18个排列。6加93乘以18正好等于1680。这个现象解释了为什么不能直接除以18——有一个等价类因为三重旋转对称规模只有其他人的三分之一。这也给后面的理论计算提供了强有力的验证。3. 组合数学的正主来了Burnside引理手算943.1 把线性排列集合和对称群摆上桌暴力搜索能给出答案但不能解释“为什么是94”。如果题目改成10万颗珠子或者要求给出通项公式暴力就无能为力了这时候必须上组合数学工具。标准的工具是Burnside引理设群G作用在集合X上那么X在G作用下的轨道数等于G中每个元素不动点数量的平均值。写成分式就是轨道数 (1/|G|) 乘以 每个g的不动点数之和。对应到这道题X就是1680个线性排列G就是正九边形的二面体群D9一共18个元素9个旋转、9个翻转。接下来只需要逐步统计每个置换到底固定了多少个排列。Burnside引理的好处在于它把“统计等价类”转化成“统计对称排列”后者的计算往往简单得多。尤其是颜色受限时只需要考虑每个循环里颜色是否一致完全不需要枚举全排列。3.2 旋转类置换大部分都是零贡献先把9个旋转元素逐个分析。旋转0度也就是恒等置换它固定所有排列所以不动点数是1680这是最大的贡献项。旋转角度不是0度时要看每个旋转把9个位置分成多少个循环。判断方法是用位移量d和总长度n求最大公约数循环数量就是gcd(n, d)。9颗珠子时位移为1、2、4、5、7、8的六种旋转公约数都是1整个排列只有一个长度为9的大循环。一个排列要在这样的旋转下保持不变必须让这个大循环里的9个位置全部同色。可题目规定每种颜色只有3颗不可能凑出9颗同色所以这6种旋转的不动点数都是0。位移为3和6的两种旋转比较特殊它们把9个位置分成三个长度为3的循环。一个排列在这类旋转下保持不变要求每个三循环内部颜色完全相同。恰好红、蓝、黄每种颜色各有3颗所以三个循环分别对应三种颜色即可一共有3的阶乘等于6种分配方案。于是这两种旋转各有6个不动点。3.3 翻转类置换为什么一个不动点都没有接下来是9个翻转操作。正九边形的每个对称轴都穿过一个珠子和它对面的边中点所以每个翻转的置换类型都是1个固定点加上4个两两互换的二元循环。要让排列在翻转下不变4个二元循环里的两个珠子必须同色1个固定点上的珠子颜色不限。假设固定点是红色那么红色总数等于2乘以红色循环数再加1。要想让红色总数等于3红色循环数只能是1蓝色总数等于2乘以蓝色循环数等于3的话无整数解所以固定点为红色时整个等式无法成立。固定点为蓝色或黄色时同理。无论固定点选什么颜色总会有一个颜色出现“2乘以循环数等于3”的矛盾。这说明9个翻转置换的不动点数全是0一分钱贡献都没有。这一点我最初也踩过坑直觉上以为轴对称至少能固定一些“颜色对称”的排列但严格推演后发现每种颜色都是奇数颗而反射交换的珠子总是成对出现导致任何颜色都无法保持奇数个。只有改变题目条件比如让某种颜色出现偶数次翻转操作才会产生非零贡献。3.4 用轨道大小拆分验证一遍把Burnside的分子加起来恒等1680加上两个旋转各6总计1692除以群大小18得到94。和暴力搜索完全一致。如果想进一步确认可以把94拆成“特殊轨道数加普通轨道数”来看。前面暴力搜索时已经发现有6个排列在旋转120度后保持不变它们是三个三循环分别被染成红、蓝、黄的那6种。这6个排列在二面体群下的轨道大小是6所以它们合并成1个样式。剩下的1674个排列每个轨道大小都是18合并成1674除以18等于93个样式。1加93等于94。这种拆分验证有一个额外价值它能帮助你快速定位Burnside计算中的错误。如果算出来的答案不是整数或者和暴力结果对不上就说明要么群元素数错了要么某个置换的循环分解错了按常量检查即可。4. 做题时的经典误区与排查思路4.1 少算翻转188就冒出来了这道题最常见的错误是把“手链”当成“项链”只考虑旋转不考虑翻转。只考虑旋转时群从18个元素变成9个元素Burnside分子没有变翻转贡献本来就是0但分母从18变成9结果就从94翻倍成188。我在真实比赛演练中见过至少两三个同学卡在这个地方。他们看到“手链”两个字没有多想直接用旋转去重得到188后怎么验都是整数差点就交了。最后是在对拍时发现暴力搜索输出94才回头读题。所以看到“手链”“手镯”“翻面”“反正面看作相同”这些词一定要把翻转纳入等价关系。反过来如果题目明确说“项链”“带编号的珠子”“区分正反面”那才只考虑旋转。一个字之差答案能差一倍。4.2 把项链和手链混为一谈与上面紧密相关的是概念混淆。很多资料里“项链计数”和“手链计数”是两个术语项链通常指正九边形在旋转下的等价类手链则额外允许翻转。命名并不完全统一因此考试时以题面为准不要靠记忆去猜。如果只是打算记住结论只算旋转时答案是188算上翻转是94。但更重要的是理解为什么。手链能翻面意味着染色序列的正反方向不造成区别相当于把每个链的行向量和它的倒序向量合并。于是等价类的数量大约减半但因为有特殊对称轨道不是精确减半。这个点还可以用来设计自测无论用数学还是代码只要把“翻转是否参与等价”作为变量做成两个函数跑出来的两个答案一个188一个94就说明程序逻辑自洽。4.3 用数学方法时选错群Burnside引理的精髓在于群的选取。这道题用的群是二面体群D9包含9个旋转和9个翻转共18个元素。如果错用循环群C9计算结果就是188如果错用正十八边形的二面体群D18那会凭空多出一倍操作答案变成非整数一测就知道有问题。还有个容易忽略的点翻转操作的数量和对称轴的位置有关。9是奇数正九边形的所有对称轴都穿珠而过所以9条翻转轴形态一致都是“1个固定点加4个二元循环”。如果总珠子数是偶数翻转轴就会分成“穿珠子”和“穿边中点”两种类型需要分别统计。我后面做扩展练习时用8颗珠子验证过一次两种翻转轴的不动点贡献完全不同必须分开算。4.4 字符串去重没做规范化出现“伪不同”暴力解法里如果只对原始线性排列去重而不考虑旋转和翻转会得到1680个“伪不同”的排列比正确答案大得多。即使考虑旋转也不够必须连翻转一起规范化。代码层面最常见的bug是旋转表示生成错误。比如只用ss截取9个字符但忘记把反转串也纳入候选或者把反转串的9个旋转表示和原串的9个旋转表示混杂在一起却忘记去重。出现这类问题时的排查思路很简单写一个断言确认规范化后的代表一定属于原排列的某个等价类同时确认同一等价类内任意两个排列规范化结果相等。我实际调试时还会单独打印某个等价类比如随机取一个排列把它的18种表示都输出肉眼扫一遍有没有遗漏。这类代码逻辑不复杂但一个边界条件写错就容易从94变成93或95非常隐蔽。5. 从手链样式到Polya计数的一般化方法5.1 Burnside和Polya之间的关系Burnside引理适用于所有需要求轨道数的有限群作用场景不限于串珠子。但它要求对每个置换单独统计不动点数量当排列空间很大时并不方便。Polya计数定理相当于在Burnside基础上的自动化只要知道每个置换的循环结构就能用颜色数的幂次直接写出不动点数。Polya定理的核心思想是一个置换的不动染色方案数等于“颜色数的循环数之幂”。前提是每种颜色的使用数量没有限制。如果题目要求红、蓝、黄各恰好3颗那就不能用简单的k的循环数次方而要回到Burnside逐个置换去数满足颜色数量限制的方案数。手链样式恰好属于有数量限制的情况所以哪怕Polya听起来很高级也不能直接套通关公式。理解了这条边界你就知道为什么手链样式最稳妥的数学解法是Burnside而不是Polya的一行公式。这也提醒我学计数算法时不要只会背公式要能说清公式的适用条件。5.2 n颗珠子k种颜色的通用思路把这道题拓展到一般情况n颗珠子均匀排列成环颜色种类k每种颜色数量不作额外限制问手链样式数。用Polya计数二面体群Dn的每个元素贡献可以用循环数表示。旋转r^d的循环数是gcd(n, d)翻转元素则分n奇偶两类奇数时每个翻转有(n1)/2个循环偶数时有n/2个循环的体型视翻转轴类型而定。如果每种颜色还有数量限制通用的做法是用多元生成函数替代单变量颜色数。设变量x、y、z分别代表三种颜色对每个置换把循环结构代入提取系数即可。以这道题为例等价于提取x三次方、y三次方、z三次方的系数再除以群大小。这套方法虽然对9颗珠子有点杀鸡用牛刀但当n变成30、50甚至上百时复杂度依然是多项式级别远远优于枚举全排列。我在准备竞赛时遇到更复杂的“环形染色限制相邻不同色”问题也是先把基础Polya练熟再叠加容斥原理处理限制。5.3 数量限制下的变形题思路手链样式的核心难点是每种颜色数量固定导致每个置换的不动点数量需要单独算。变形题可以有很多方向比如把9颗改成8颗每种颜色数量变成2、2、4这时候翻转操作就会产生非零不动点又比如要求同色珠子不能相邻那就需要用容斥或者动态规划在Burnside里做内部计数。做这些变形时最实用的方法论是先在带编号的位置上建立计数模型再对每个群元素施加“同循环同色”的约束最后求平均。无论题目怎么变这个框架都不会变。当初我在一个训练营里做过一组对比题把n从5改到10k从2改到4逐步验算确实能感受到公式化方法的威力。不过方法再通用也要警惕群元素本身的枚举。n较大时二面体群大小是2n每个置换算一次不动点整体依然可以接受。只要置换循环分解写对剩下的就是组合计数基本功。6. 我的实战心得6.1 比赛里的时间分配先暴力后理论这种计数题在比赛里往往只有一分填空题或一个小问不值得在一开始就埋头推Burnside。我的习惯是拿到题先花30秒写暴力代码把答案跑出来哪怕代码跑10秒也无所谓。有了基准答案再做数学推导推导的每一步都可以和已知答案对拍。如果数学算到一半发现对不上就说明中间某个环节出了问题这时可以缩小范围先单独验算旋转贡献再单独验算翻转贡献最后验算群元素数量。有一次我算反射轴贡献时漏了一种情况答案差了9就是靠这个分段排查找出来的。6.2 数学结果和代码结果对不上时的排查顺序我总结了一个固定排查顺序。第一步检查群大小是不是该用18却用了9。第二步检查循环分解特别是旋转位移3和6容易把gcd算错成1。第三步检查不动点计数如果用了Polya定理的幂次形式要立刻意识到颜色数量限制可能让这个公式失效。第四步检查代码规范化单独打印一个等价类的全部表示确认没有生成重复或遗漏。这个顺序帮我省了大量时间。有一次朋友把代码写成只考虑循环同构漏了翻转结果答案188按第一步检查一眼定位。还有一次是某篇文章把答案写成376我拿暴力程序一跑就知道它把“颜色带编号的珠子”当成10颗在算和题意完全不符。6.3 一串真实手链告诉我的事最后聊点题外话。我照着94种样式里的某一种真的买珠子串了一条手链。串完才意识到数学模型里的“翻面等价”在物理世界里不是完全无代价的——珠子有厚度正反面的纹理可能有细微差别串线方向也会影响佩戴效果。但从算法竞赛角度题目把珠子抽象成只有颜色区别翻面看成几何对称等价是完全合理的建模。学组合数学最大的乐趣就在这里一个问题被抽象成群和等价类之后答案会变得异常干净。94这个数字表面上是计数结果背后其实是二面体群作用在颜色排列上的轨道结构。理解这一点比单纯记住答案有用得多。如果下次再遇到类似的手链、项链、圆桌座位问题时我建议你也先暴力算出基准答案再用Burnside或者Polaya提炼通式。这个过程走一遍比刷十道普通计数题都更能建立感觉。
如果给你9颗珠子红、蓝、黄各3颗让你串一条手链你觉得最后能得到多少种真正不同的样式我第一次认真算这道题时随口猜了个大概几百上千结果程序跑出来是个很不起眼的94。这个答案让我愣了很久因为直觉上9颗珠子能摆出的线性排列明明有1680种怎么一上手链就缩水成两位数了。后来把旋转和翻转的对称性逐项算清楚才明白这道手链样式组合数学题藏得有多深。这篇就把完整的拆题、暴力验证、理论计算和踩坑过程都写出来给准备算法竞赛、或者想彻底搞懂Polya计数的朋友参考。1. 手链样式这道题题面里到底藏着什么1.1 把题面翻译成数学模型题目表面上是手工问题三种颜色各3颗珠子穿成环形手链问有多少种不同样式。但一旦要精确计算就得先回答一个关键问题——“不同样式”到底怎么定义数学上的定义是两条手链如果能通过旋转或者翻转变成同一条就视为同一种样式。这里有两个隐藏约束值得细说。第一珠子只有颜色区别没有编号所以“红1、红2、红3”互换位置不算新样式。第二手链是环形且可翻面的这与“项链”有微妙区别。不少题目会把项链定义成只能旋转、不能翻转手链则允许翻面。手链样式的计数结果94就是同时把旋转和翻转都算作同构得到的。如果给9个位置编号不考虑对称性只安排颜色排列数是9的阶乘除以三个3的阶乘也就是1680。这1680个带编号排列是后面所有计算的出发点。手链样式问题本质上就是研究这1680个排列在“旋转”和“翻转”操作之下会合并成多少个等价类。1.2 为什么“样式相同”是一个等价关系“旋转后相同”“翻转后相同”听起来很直观但值得从数学上确认一下它确实是等价关系因为后面用群论计算时靠的就是这条性质。假设定义两个线性排列等价当且仅当其中一个能经过若干次旋转、翻转变成另一个。那么自反性显然成立任何排列旋转0度等于自己对称性也成立因为每次旋转、翻转都有逆操作传递性同样成立两次操作的复合还是旋转或翻转操作。满足这三条就能把1680个排列划分成互不相交的等价类每个等价类对应一种手链样式。这一步很多初学者会忽略直接拿枚举结果除以18旋转9种乘翻转2种想当然去算最后得到93.33这种非整数就发现不对劲了。原因就在于部分排列有特殊的对称性导致它们的等价类大小并不是统一的18。后面用Burnside引理处理的就是这种不均等。2. 不想数学推导那就先把暴力搜索跑起来2.1 生成1680个线性排列竞赛里遇到拿不准的计数题我习惯先写一个暴力程序把答案跑出来哪怕慢一点也无所谓。这道题数据规模很小9颗珠子就算全排列也只有36万种计算机完全扛得住。第一步是生成所有颜色不同的线性排列。直接对字符串RRRBBBYYY做全排列再用集合去重就能得到1680个有效排列。代码如下from itertools import permutations base RRRBBBYYY unique_perms set(permutations(base)) print(len(unique_perms)) # 输出 1680这里有个细节permutations(base)本身会产生362880个结果因为我用了可迭代对象而不是原始字符串列表所以包含大量因为相同颜色珠子互换而完全相同的排列。用set去重后才得到真正的1680个颜色组合。2.2 用最小表示法去重拿到1680个线性排列后第二步是对每个排列生成它的全部等价表示再统一去重。旋转操作容易实现把字符串首尾相接依次从每个位置截取长度为9的子串就能得到9种旋转结果。翻转操作对环形链来说等价于把线性排列倒序后再旋转所以把字符串反转之后再同样取9种旋转结果即可。把所有可能的18种表示放进一个列表取字典序最小的那个作为这个等价类的“代表”最后统计代表的总数即可。完整代码如下def normalize(s: str) - str: n len(s) doubled s s candidates [doubled[i:in] for i in range(n)] rev s[::-1] rev_doubled rev rev candidates [rev_doubled[i:in] for i in range(n)] return min(candidates) styles set() for p in unique_perms: styles.add(normalize(.join(p))) print(len(styles)) # 输出 94这段代码的思路可以扩展到任意环形去重场景。最小表示法不要求真的“旋转珠子”只需要保证同一个等价类无论从哪个表示进入最后都输出同一个字符串。这里用字典序min作为规范化函数简单可靠。2.3 先跑一个能让自己信服的答案暴力跑出94之后最好再验证一下这个结果没有手滑。方法是用另一种方式统计等价类大小之和遍历1680个排列每遇到一个未标记的排列就把它的18种表示全部标出来数一数它所在等价类实际有多大。把各个等价类的大小加起来应该重新得到1680。我实测下来的分布很有规律其中一个等价类比较特殊只包含6个排列其余93个等价类每个包含18个排列。6加93乘以18正好等于1680。这个现象解释了为什么不能直接除以18——有一个等价类因为三重旋转对称规模只有其他人的三分之一。这也给后面的理论计算提供了强有力的验证。3. 组合数学的正主来了Burnside引理手算943.1 把线性排列集合和对称群摆上桌暴力搜索能给出答案但不能解释“为什么是94”。如果题目改成10万颗珠子或者要求给出通项公式暴力就无能为力了这时候必须上组合数学工具。标准的工具是Burnside引理设群G作用在集合X上那么X在G作用下的轨道数等于G中每个元素不动点数量的平均值。写成分式就是轨道数 (1/|G|) 乘以 每个g的不动点数之和。对应到这道题X就是1680个线性排列G就是正九边形的二面体群D9一共18个元素9个旋转、9个翻转。接下来只需要逐步统计每个置换到底固定了多少个排列。Burnside引理的好处在于它把“统计等价类”转化成“统计对称排列”后者的计算往往简单得多。尤其是颜色受限时只需要考虑每个循环里颜色是否一致完全不需要枚举全排列。3.2 旋转类置换大部分都是零贡献先把9个旋转元素逐个分析。旋转0度也就是恒等置换它固定所有排列所以不动点数是1680这是最大的贡献项。旋转角度不是0度时要看每个旋转把9个位置分成多少个循环。判断方法是用位移量d和总长度n求最大公约数循环数量就是gcd(n, d)。9颗珠子时位移为1、2、4、5、7、8的六种旋转公约数都是1整个排列只有一个长度为9的大循环。一个排列要在这样的旋转下保持不变必须让这个大循环里的9个位置全部同色。可题目规定每种颜色只有3颗不可能凑出9颗同色所以这6种旋转的不动点数都是0。位移为3和6的两种旋转比较特殊它们把9个位置分成三个长度为3的循环。一个排列在这类旋转下保持不变要求每个三循环内部颜色完全相同。恰好红、蓝、黄每种颜色各有3颗所以三个循环分别对应三种颜色即可一共有3的阶乘等于6种分配方案。于是这两种旋转各有6个不动点。3.3 翻转类置换为什么一个不动点都没有接下来是9个翻转操作。正九边形的每个对称轴都穿过一个珠子和它对面的边中点所以每个翻转的置换类型都是1个固定点加上4个两两互换的二元循环。要让排列在翻转下不变4个二元循环里的两个珠子必须同色1个固定点上的珠子颜色不限。假设固定点是红色那么红色总数等于2乘以红色循环数再加1。要想让红色总数等于3红色循环数只能是1蓝色总数等于2乘以蓝色循环数等于3的话无整数解所以固定点为红色时整个等式无法成立。固定点为蓝色或黄色时同理。无论固定点选什么颜色总会有一个颜色出现“2乘以循环数等于3”的矛盾。这说明9个翻转置换的不动点数全是0一分钱贡献都没有。这一点我最初也踩过坑直觉上以为轴对称至少能固定一些“颜色对称”的排列但严格推演后发现每种颜色都是奇数颗而反射交换的珠子总是成对出现导致任何颜色都无法保持奇数个。只有改变题目条件比如让某种颜色出现偶数次翻转操作才会产生非零贡献。3.4 用轨道大小拆分验证一遍把Burnside的分子加起来恒等1680加上两个旋转各6总计1692除以群大小18得到94。和暴力搜索完全一致。如果想进一步确认可以把94拆成“特殊轨道数加普通轨道数”来看。前面暴力搜索时已经发现有6个排列在旋转120度后保持不变它们是三个三循环分别被染成红、蓝、黄的那6种。这6个排列在二面体群下的轨道大小是6所以它们合并成1个样式。剩下的1674个排列每个轨道大小都是18合并成1674除以18等于93个样式。1加93等于94。这种拆分验证有一个额外价值它能帮助你快速定位Burnside计算中的错误。如果算出来的答案不是整数或者和暴力结果对不上就说明要么群元素数错了要么某个置换的循环分解错了按常量检查即可。4. 做题时的经典误区与排查思路4.1 少算翻转188就冒出来了这道题最常见的错误是把“手链”当成“项链”只考虑旋转不考虑翻转。只考虑旋转时群从18个元素变成9个元素Burnside分子没有变翻转贡献本来就是0但分母从18变成9结果就从94翻倍成188。我在真实比赛演练中见过至少两三个同学卡在这个地方。他们看到“手链”两个字没有多想直接用旋转去重得到188后怎么验都是整数差点就交了。最后是在对拍时发现暴力搜索输出94才回头读题。所以看到“手链”“手镯”“翻面”“反正面看作相同”这些词一定要把翻转纳入等价关系。反过来如果题目明确说“项链”“带编号的珠子”“区分正反面”那才只考虑旋转。一个字之差答案能差一倍。4.2 把项链和手链混为一谈与上面紧密相关的是概念混淆。很多资料里“项链计数”和“手链计数”是两个术语项链通常指正九边形在旋转下的等价类手链则额外允许翻转。命名并不完全统一因此考试时以题面为准不要靠记忆去猜。如果只是打算记住结论只算旋转时答案是188算上翻转是94。但更重要的是理解为什么。手链能翻面意味着染色序列的正反方向不造成区别相当于把每个链的行向量和它的倒序向量合并。于是等价类的数量大约减半但因为有特殊对称轨道不是精确减半。这个点还可以用来设计自测无论用数学还是代码只要把“翻转是否参与等价”作为变量做成两个函数跑出来的两个答案一个188一个94就说明程序逻辑自洽。4.3 用数学方法时选错群Burnside引理的精髓在于群的选取。这道题用的群是二面体群D9包含9个旋转和9个翻转共18个元素。如果错用循环群C9计算结果就是188如果错用正十八边形的二面体群D18那会凭空多出一倍操作答案变成非整数一测就知道有问题。还有个容易忽略的点翻转操作的数量和对称轴的位置有关。9是奇数正九边形的所有对称轴都穿珠而过所以9条翻转轴形态一致都是“1个固定点加4个二元循环”。如果总珠子数是偶数翻转轴就会分成“穿珠子”和“穿边中点”两种类型需要分别统计。我后面做扩展练习时用8颗珠子验证过一次两种翻转轴的不动点贡献完全不同必须分开算。4.4 字符串去重没做规范化出现“伪不同”暴力解法里如果只对原始线性排列去重而不考虑旋转和翻转会得到1680个“伪不同”的排列比正确答案大得多。即使考虑旋转也不够必须连翻转一起规范化。代码层面最常见的bug是旋转表示生成错误。比如只用ss截取9个字符但忘记把反转串也纳入候选或者把反转串的9个旋转表示和原串的9个旋转表示混杂在一起却忘记去重。出现这类问题时的排查思路很简单写一个断言确认规范化后的代表一定属于原排列的某个等价类同时确认同一等价类内任意两个排列规范化结果相等。我实际调试时还会单独打印某个等价类比如随机取一个排列把它的18种表示都输出肉眼扫一遍有没有遗漏。这类代码逻辑不复杂但一个边界条件写错就容易从94变成93或95非常隐蔽。5. 从手链样式到Polya计数的一般化方法5.1 Burnside和Polya之间的关系Burnside引理适用于所有需要求轨道数的有限群作用场景不限于串珠子。但它要求对每个置换单独统计不动点数量当排列空间很大时并不方便。Polya计数定理相当于在Burnside基础上的自动化只要知道每个置换的循环结构就能用颜色数的幂次直接写出不动点数。Polya定理的核心思想是一个置换的不动染色方案数等于“颜色数的循环数之幂”。前提是每种颜色的使用数量没有限制。如果题目要求红、蓝、黄各恰好3颗那就不能用简单的k的循环数次方而要回到Burnside逐个置换去数满足颜色数量限制的方案数。手链样式恰好属于有数量限制的情况所以哪怕Polya听起来很高级也不能直接套通关公式。理解了这条边界你就知道为什么手链样式最稳妥的数学解法是Burnside而不是Polya的一行公式。这也提醒我学计数算法时不要只会背公式要能说清公式的适用条件。5.2 n颗珠子k种颜色的通用思路把这道题拓展到一般情况n颗珠子均匀排列成环颜色种类k每种颜色数量不作额外限制问手链样式数。用Polya计数二面体群Dn的每个元素贡献可以用循环数表示。旋转r^d的循环数是gcd(n, d)翻转元素则分n奇偶两类奇数时每个翻转有(n1)/2个循环偶数时有n/2个循环的体型视翻转轴类型而定。如果每种颜色还有数量限制通用的做法是用多元生成函数替代单变量颜色数。设变量x、y、z分别代表三种颜色对每个置换把循环结构代入提取系数即可。以这道题为例等价于提取x三次方、y三次方、z三次方的系数再除以群大小。这套方法虽然对9颗珠子有点杀鸡用牛刀但当n变成30、50甚至上百时复杂度依然是多项式级别远远优于枚举全排列。我在准备竞赛时遇到更复杂的“环形染色限制相邻不同色”问题也是先把基础Polya练熟再叠加容斥原理处理限制。5.3 数量限制下的变形题思路手链样式的核心难点是每种颜色数量固定导致每个置换的不动点数量需要单独算。变形题可以有很多方向比如把9颗改成8颗每种颜色数量变成2、2、4这时候翻转操作就会产生非零不动点又比如要求同色珠子不能相邻那就需要用容斥或者动态规划在Burnside里做内部计数。做这些变形时最实用的方法论是先在带编号的位置上建立计数模型再对每个群元素施加“同循环同色”的约束最后求平均。无论题目怎么变这个框架都不会变。当初我在一个训练营里做过一组对比题把n从5改到10k从2改到4逐步验算确实能感受到公式化方法的威力。不过方法再通用也要警惕群元素本身的枚举。n较大时二面体群大小是2n每个置换算一次不动点整体依然可以接受。只要置换循环分解写对剩下的就是组合计数基本功。6. 我的实战心得6.1 比赛里的时间分配先暴力后理论这种计数题在比赛里往往只有一分填空题或一个小问不值得在一开始就埋头推Burnside。我的习惯是拿到题先花30秒写暴力代码把答案跑出来哪怕代码跑10秒也无所谓。有了基准答案再做数学推导推导的每一步都可以和已知答案对拍。如果数学算到一半发现对不上就说明中间某个环节出了问题这时可以缩小范围先单独验算旋转贡献再单独验算翻转贡献最后验算群元素数量。有一次我算反射轴贡献时漏了一种情况答案差了9就是靠这个分段排查找出来的。6.2 数学结果和代码结果对不上时的排查顺序我总结了一个固定排查顺序。第一步检查群大小是不是该用18却用了9。第二步检查循环分解特别是旋转位移3和6容易把gcd算错成1。第三步检查不动点计数如果用了Polya定理的幂次形式要立刻意识到颜色数量限制可能让这个公式失效。第四步检查代码规范化单独打印一个等价类的全部表示确认没有生成重复或遗漏。这个顺序帮我省了大量时间。有一次朋友把代码写成只考虑循环同构漏了翻转结果答案188按第一步检查一眼定位。还有一次是某篇文章把答案写成376我拿暴力程序一跑就知道它把“颜色带编号的珠子”当成10颗在算和题意完全不符。6.3 一串真实手链告诉我的事最后聊点题外话。我照着94种样式里的某一种真的买珠子串了一条手链。串完才意识到数学模型里的“翻面等价”在物理世界里不是完全无代价的——珠子有厚度正反面的纹理可能有细微差别串线方向也会影响佩戴效果。但从算法竞赛角度题目把珠子抽象成只有颜色区别翻面看成几何对称等价是完全合理的建模。学组合数学最大的乐趣就在这里一个问题被抽象成群和等价类之后答案会变得异常干净。94这个数字表面上是计数结果背后其实是二面体群作用在颜色排列上的轨道结构。理解这一点比单纯记住答案有用得多。如果下次再遇到类似的手链、项链、圆桌座位问题时我建议你也先暴力算出基准答案再用Burnside或者Polaya提炼通式。这个过程走一遍比刷十道普通计数题都更能建立感觉。
实现：从slack优化到BFS版完整模板)
