尧图网站开发 
1. 环形染色问题到底在求什么模型定义与经典公式“环形染色问题”这名字听起来像是小学奥数里的脑筋急转弯但它在组合数学和算法竞赛里分量真不小。我第一次认真和它打交道是在刷一道“正 n 边形顶点染色”的题目时被卡了半天后来翻组合数学教材才发现它正是图染色理论里“环图 C_n 的色多项式”的一个漂亮特例。别被这些名词吓到剥开外壳问题本身非常朴素。经典模型是这样的在一个圆环上有 n 个区域或者说正 n 边形的 n 个顶点用 m 种颜色给这些区域染色要求相邻两个区域颜色不能相同。问一共有多少种不同的染色方案。注意这里的“不同”默认是区域编号不同也就是每个位置是固定的旋转对称不算同一种翻转对称也不算同一种。先把这个前提钉死后面所有推导才有意义。这个问题的结论可以浓缩成一个公式f(n) (m - 1)^n (-1)^n (m - 1)其中 n 是区域数量m 是颜色数量f(n) 就是合法染色方案数。我第一次看到这个公式的时候第一反应是为什么这么简洁组合数学里带 (-1)^n 的闭式结果通常背后都藏着容斥或者递推的影子。后来把两种推导都捋了一遍发现这个公式几乎是把“环结构中最核心的对称性”给榨干了。本文接下来就围绕这个公式展开先讲它怎么来的再讲怎么验证它然后讲怎么用代码算它最后聊几个常见的变体和坑。适合数学竞赛党、算法竞赛选手以及任何对组合计数感兴趣的读者。2. 公式怎么来两种主流推导一次性讲透2.1 递推法从链到环剪一刀就够了递推法的思路特别适合作为第一直觉环比链多一条边那能不能先处理链再想办法去掉那条多出来的限制先把环在某一条边上剪开你会发现它变成了一条有 n 个点的链这 n 个点首尾不再相邻只剩下“内部相邻点不同色”的条件。一条 n 个点的链第一个点可以随便选有 m 种之后每个点只要避开前一个点的颜色都有 m - 1 种选择。所以链的总染色数是链方案数 m × (m - 1)^(n - 1)现在的问题是这些链方案里有多少个在把首尾接回去之后仍然合法显然只有“首尾两点颜色不同”的方案接成环后才满足相邻不同色的条件。换句话说合法的环染色数 链方案数 - 首尾同色的链方案数。麻烦的是“首尾同色”的链方案数怎么算。这里有个非常漂亮的观察如果一条链的首尾同色把这两个点合并成一个点得到的是一个有 n - 1 个点的环而且这个合并后的环本身一定合法——为什么因为首尾这两个点原本分别和它们内侧的相邻点颜色不同合并成同一个点后这个新点仍然区别于它两侧的邻点。反过来任意一个 n - 1 个点的合法环染色随便选一个点把它“拆开”成两个同色相邻点也就得到了一条首尾同色的 n 点链。这是一一对应。所以立刻得到递推关系f(n) m × (m - 1)^(n - 1) - f(n - 1)边界条件是 f(2) m × (m - 1)因为两个区域围成一个圈本质上只要求这两个区域不同色。这个一阶递推很好解。先猜一个形状再归纳验证令 f(n) (m - 1)^n (-1)^n (m - 1)。代入递推的右边m × (m - 1)^(n - 1) - [ (m - 1)^(n - 1) (-1)^(n - 1)(m - 1) ] (m - 1)^n - (-1)^(n - 1)(m - 1) (m - 1)^n (-1)^n (m - 1)完美闭环。递推法最大的价值在于它把环和链的关系讲清楚了也让 n1 和 n2 这种边界情况原形毕露后面避坑环节我还会再强调。2.2 容斥法那个最容易漏掉的修正项如果递推法靠的是“剪一刀”的几何直觉容斥法靠的就是纯粹的集合计数。这个方法在推导时有一个非常隐蔽的细节很多资料里都一笔带过但恰恰是最容易翻车的地方。把 n 个点看成编号 1 到 n边有 n 条边 1 连接点 1 和 2边 2 连接点 2 和 3依此类推边 n 连接点 n 和点 1。总方案数显然是 m^n因为每个点都有 m 种颜色可选。现在要扣除那些“至少有一条边的两端同色”的方案。定义事件 A_i 表示“第 i 条边的两个端点颜色相同”那么合法方案数就是所有 A_i 都不发生的方案数。容斥原理登场。对任意一组被选中的边集 S如果 |S| k 且 k n这些边在 n 个点的环上不可能构成闭合回路它们只会把 n 个点切成 n - k 个连通块每个连通块内部颜色必须一样。于是方案数为 m^(n - k)。从 k 条边中选出这个边集有 C(n, k) 种选法这里不需要纠结连通块长什么样因为每个连通块贡献一个自由颜色方案数只依赖于块数。但是当 k n 时也就是 n 条边全被选中情况就完全变了所有点连成一个大连通块整环只能是一种颜色方案数是 m而不是直觉上的 m^(n - n) m^0 1。这一个点的差异正是环形结构区别于普通图的本质特征。于是合法数 Σ_{k0}^{n-1} (-1)^k C(n,k) m^(n-k) (-1)^n × m把 k n 那一项补成统一形式再减掉修正项合法数 Σ_{k0}^{n} (-1)^k C(n,k) m^(n-k) - (-1)^n (-1)^n × m前面那一整坨正是二项式展开 (m - 1)^n。所以最终得到f(n) (m - 1)^n (-1)^n (m - 1)容斥法的好处是完全从“约束条件”出发不依赖首尾相接的几何直觉但它要求你对“选满所有边”这个特殊情况足够敏感。很多初学者在背公式的时候完全不知道这个修正项的存在自然不会明白为什么不是单纯等于 (m - 1)^n。2.3 两种推导方式怎么选递推法和容斥法不是互斥的它们恰好从两个角度揭示了同一个公式递推法告诉你这是环与链之间的转换关系容斥法告诉你这是“全选所有边”这个特殊集合带来的修正。实际使用中如果只是求方案数直接套公式或者用递推都行但如果题目换了个限制条件比如“某些边不允许同色”“某些点强制同色”这时候容斥法的框架往往更容易扩展因为它本质上就是在处理“强制条件集合”。我自己的习惯是先在草稿纸上用递推法快速写出公式再用容斥法核对一遍尤其是检查 k n 的修正项有没有漏。3. 别急着套公式先记牢这些特例与自查表3.1 最经典的例子正五边形的五顶点染色在数学竞赛里“环形染色问题”最常见的出场方式就是“正五边形的五个顶点用五种颜色染色相邻顶点不同色求方案数”。不要犹豫直接代公式m 5n 5。f(5) (5 - 1)^5 (-1)^5 × (5 - 1) 4^5 - 4 1024 - 4 10201020 种。这个数字看着不大但如果有人试图枚举会发现五个点的限制是环环相扣的枚举很容易重复或遗漏。公式的好处在这个时候体现得淋漓尽致。3.2 二色和三色的特殊情况很直观用两种颜色给环染色结果非常依赖 n 的奇偶性。m 2 时代入公式f(n) 1^n (-1)^n × 1 1 (-1)^n也就是说n 为偶数时方案数为 2n 为奇数时方案数为 0。这在直觉上完全成立两个颜色唯一可能的环形交替模式是 A-B-A-B...n 为偶数才能首尾接上而且只有两种颜色分配方式奇数是根本绕不回来的。同样三种颜色给三个区域染色也就是三角形的三个顶点两两相邻必须三色全不同方案数是 3 × 2 × 1 6。代入公式 m 3n 3f(3) 2^3 - 2 6完全吻合。这些特例不是用来背的是用来在考试或写代码时快速校验公式有没有用错的。3.3 小数据自查表我自己刷题时有个习惯套公式算完一定要先验一组小数据确认没有方向性错误。下面这张表列了 m 2、3、4 时前几个 n 的合法方案数建议读者自己拿公式也算一遍这个过程能帮你发现很多理解上的偏差。nm2m3m4226123062442188450302406266732以 m 4、n 4 为例公式给出 3^4 3 84。这个数可以这样交叉验证四个点围成一个四边形先按链算 4 × 3^3 108再减去首尾同色对应 f(3) 24得到 84。多一条验证路径少一分翻车风险。4. 代码实现三种写法的复杂度与适用场景4.1 O(n) 动态规划思路最直观如果不想背公式动态规划是最稳的保底方案。状态设计非常自然维护两个值一个是当前点和第一个点颜色相同的方案数 same一个是当前点和第一个点颜色不同的方案数 diff。初始时第一个点有 m 种颜色可选所以 same mdiff 0。每加入一个新点状态转移如下如果新点要和第一个点同色那它只有 1 种选择取第一个点的颜色而且要求上一个点和第一个点颜色不同否则相邻会撞色。所以新的 same 旧 diff。如果新点要和第一个点不同色分两种情况上一个点和第一个点同色那么新点不能和第一个点同色有 m - 1 种选择上一个点和第一个点不同色那么新点既要避开第一个点也要避开上一个点有 m - 2 种选择。所以新的 diff 旧 same × (m - 1) 旧 diff × (m - 2)。最终答案是处理完 n 个点后的 diff。def ring_color_dp(m, n): if n 1: return m same m diff 0 for _ in range(2, n 1): same, diff diff, same * (m - 1) diff * (m - 2) return diff这个 DP 的优点是很容易扩展到更复杂的约束比如加了“最多连续两个同色”之类的限制只需多开一维状态。缺点是当 n 达到 10^18 时O(n) 循环直接超时。4.2 O(log n) 矩阵快速幂应对超大 n一旦 n 的规模上亿DP 就不行了。好在上面那个递推是一个标准的线性递推可以写成 2×2 矩阵乘法。状态向量取 [same, diff]转移矩阵是M [[0, 1], [m - 1, m - 2]]因为same 0 × 旧same 1 × 旧diffdiff (m - 1) × 旧same (m - 2) × 旧diff初始向量 [m, 0]应用 M^(n-1) 后取第二维就是答案。def mat_mul(A, B, mod): return [ [(A[0][0] * B[0][0] A[0][1] * B[1][0]) % mod, (A[0][0] * B[0][1] A[0][1] * B[1][1]) % mod], [(A[1][0] * B[0][0] A[1][1] * B[1][0]) % mod, (A[1][0] * B[0][1] A[1][1] * B[1][1]) % mod], ] def mat_pow(M, p, mod): res [[1, 0], [0, 1]] while p: if p 1: res mat_mul(res, M, mod) M mat_mul(M, M, mod) p 1 return res def ring_color_matrix(m, n, mod): if n 1: return m % mod M [[0, 1], [(m - 1) % mod, (m - 2) % mod]] M mat_pow(M, n - 1, mod) return (M[1][0] * m) % mod矩阵快速幂的比赛标准姿势几乎所有支持快速幂的题目里都能用。不过说实话如果只是环形染色这一道题直接套公式快速幂就够了矩阵反而有点杀鸡用牛刀。它真正的价值在于当你需要把“环形染色”作为整个大算法的一个子模块时矩阵做法可以无缝嵌入。4.3 O(log n) 公式快速幂最简洁也最容易踩坑既然闭式公式已经写出来了为什么还要绕一圈直接快速幂算 (m - 1)^n再加上 (-1)^n 的修正项就行。def ring_color_formula(m, n, mod): if n 1: return m % mod ans pow(m - 1, n, mod) if n 1: ans (ans - (m - 1)) % mod else: ans (ans (m - 1)) % mod return ans这里有两个坑必须提醒。第一如果 m 和 n 都很大而且要对某个模数取模那么 (m - 1) 也要先取模再加或减不能把原始值带进去。第二如果要求输出的是非负整数Python 的%运算天然保证非负但 C 里要写成(ans mod) % mod的形状否则负数取模会给你意想不到的结果。公式写的短不代表它不重要恰恰相反它是三种写法里数值上最可控的也是我实际刷题时用得最多的。5. 变体与扩展从基础题到进阶题5.1 旋转和翻转要不要算同一种“环形染色问题”默认区域编号固定旋转或翻转后算不同方案。但现实场景里“圆环”经常没有那么强的编号感一条项链在手腕上旋转一下还是同一条一面圆桌在翻面之后摆法也一样。一旦题目要求“旋转或翻转视为同一种”基础公式就不能直接用了必须上 Burnside 引理。对称计数的一般流程是枚举置换群里的每个置换旋转 k 个位置、翻转轴等数出这个置换下保持不变的颜色方案数然后取平均值。对于环形染色旋转 k 个单位的不动点实际上等价于在一个更小的环上染色小环的规模是循环数因此仍然可以套用经典公式只是参数变了。翻转的不动点则需要单独讨论通常比旋转更麻烦。这类问题在“项链染色”“手镯染色”的经典组合计数题里出现频率很高以后遇到建议单独整理一篇这里点到为止。5.2 添加连续同色数量限制如果题目从“相邻不同色”改成“相邻最多允许两个同色不允许连续三个同色”公式就失效了因为约束不再只是边上的二元关系而是涉及长度为三的窗口。此时动态规划仍然适用只是状态要扩展一维记录当前点和第一个点颜色是否一致、以及当前已经连续了几个相同颜色。例如可以设 dp[i][j][c] 表示前 i 个点、第 i 个点与第一个点颜色关系为 j0 或 1、当前末尾连续同色长度为 c 的方案数。转移枚举新点颜色与上一个点是否相同即可。虽然状态数翻了常数倍但只要约束是“连续段的长度限制”这类 DP 就永远不会失效。这也是我建议你一定要理解 DP 解法而不是只会背公式的原因。5.3 必须 / 禁止使用某种颜色的计数再举一个常见变体用 m 种颜色给 n 个区域环形染色相邻不同色且规定颜色 1 至少出现一次。直接算“至少一次”常常让人头大但计算“一次都不出现”反而简单——把颜色 1 从色盘里删掉剩下 m - 1 种颜色继续做普通环形染色方案数是 f(n, m - 1)。于是答案就是总数减去这个“禁用颜色 1”的方案数至少出现一次 f(n, m) - f(n, m - 1)这类“强制出现”“禁止出现”的题型本质上是容斥思想在公式层面的应用。遇到更复杂的组合约束比如“颜色 1 和颜色 2 都必须出现”就用容斥原理逐层展开每一步都能套用经典公式。5.4 与色多项式的关系图论里有一个概念叫色多项式对一个图 G用 q 种颜色给顶点染色相邻顶点不同色记为 P(G, q)。对环图 C_n色多项式恰好就是P(C_n, q) (q - 1)^n (-1)^n (q - 1)所以你花费十几分钟推出来的环形染色公式在齐次坐标下其实就是环图的色多项式。理解了这一点遇到“若干个环拼在一起”的组合图时就不会觉得无从下手——很多情况下可以先拆成独立的环分别计数再用乘法原理合并。这也是为什么我说这是一个“入门简单、上限很高”的模型。6. 踩坑实录环形染色最容易翻车的四个地方6.1 n1 和 n2 的边界真的不是小事n 1 的时候环退化成单个点它和自己是同一点不存在“相邻区域颜色不同”的矛盾。如果你默认每个区域是独立的染色数应该是 m。但代入公式 (m - 1)^1 (-1)^1 (m - 1) 0显然是矛盾的。为什么因为递推法的“剪开”操作、容斥法的“选中全部 n 条边成环”描述都默认 n ≥ 2。处理 n 1 之前必须先看题目怎么定义“相邻”。如果题目没特别说明我会直接按特殊情况返回 m并在题解里明确标注。n 2 也好不到哪去两点的“环”其实只有一条边公式给的是 m(m - 1)但如果题目把两个区域看得更复杂需要小心读题。6.2 容斥全选边集时m^0 是个大坑我在 2.2 节特别强调了 k n 时的修正项。很多人第一次自己推容斥都会自然地写出Σ_{k0}^{n} (-1)^k C(n,k) m^(n-k)然后得意洋洋收工结果发现少了一项 (-1)^n (m - 1)。原因就在于把“选满所有 n 条边”理解成了“n 个连通块各 1 种颜色”但n条边全选后实际是 1 个连通块m 种颜色。这种错误极其隐蔽因为你对着二项式展开检查时会觉得每一步都顺理成章。所以我建议在推导容斥时把 k n 和 k n 分开写最后再合并。6.3 取模运算里负数处理不当直接错算法题里常见的模数是 10^9 7公式里的 (-1)^n 修正项很容易导致中间结果出现负数。C 里可以直接这样写long long ans mod_pow(m - 1, n, MOD); long long extra (m - 1) % MOD; if (n 1) ans (ans - extra MOD) % MOD; else ans (ans extra) % MOD;多写一个MOD能省下无数个晚上的排查时间。我见过太多次因为负取模导致 WA 到怀疑人生的案例这不是数学问题是语言细节。6.4 先确认“区域是否编号”再决定用哪个公式最后这个是审题层面的坑。同样一句话“把 n 个点围成一圈染色”如果题目说“圆形排列”“项链”大概率要考虑旋转等价如果题目说“正 n 边形的顶点依次编号”那就是标准的编号环。前者需要 Burnside后者才是本文公式的直接适用范围。我建议拿到题先圈出关键词出现“编号”“依次”“固定位置”直接套公式出现“旋转”“翻转”“等价”立刻切到置换群计数框架。这个模型本身不难但它像一面镜子把你对“环的对称性”理解得够不够透彻照得清清楚楚。我自己的体会是与其机械记公式不如把递推法那“剪一刀”的思路刻在脑子里遇到再复杂的环形变体先剪成链再一步步加限制回来基本不会走偏。 
1. 环形染色问题到底在求什么模型定义与经典公式“环形染色问题”这名字听起来像是小学奥数里的脑筋急转弯但它在组合数学和算法竞赛里分量真不小。我第一次认真和它打交道是在刷一道“正 n 边形顶点染色”的题目时被卡了半天后来翻组合数学教材才发现它正是图染色理论里“环图 C_n 的色多项式”的一个漂亮特例。别被这些名词吓到剥开外壳问题本身非常朴素。经典模型是这样的在一个圆环上有 n 个区域或者说正 n 边形的 n 个顶点用 m 种颜色给这些区域染色要求相邻两个区域颜色不能相同。问一共有多少种不同的染色方案。注意这里的“不同”默认是区域编号不同也就是每个位置是固定的旋转对称不算同一种翻转对称也不算同一种。先把这个前提钉死后面所有推导才有意义。这个问题的结论可以浓缩成一个公式f(n) (m - 1)^n (-1)^n (m - 1)其中 n 是区域数量m 是颜色数量f(n) 就是合法染色方案数。我第一次看到这个公式的时候第一反应是为什么这么简洁组合数学里带 (-1)^n 的闭式结果通常背后都藏着容斥或者递推的影子。后来把两种推导都捋了一遍发现这个公式几乎是把“环结构中最核心的对称性”给榨干了。本文接下来就围绕这个公式展开先讲它怎么来的再讲怎么验证它然后讲怎么用代码算它最后聊几个常见的变体和坑。适合数学竞赛党、算法竞赛选手以及任何对组合计数感兴趣的读者。2. 公式怎么来两种主流推导一次性讲透2.1 递推法从链到环剪一刀就够了递推法的思路特别适合作为第一直觉环比链多一条边那能不能先处理链再想办法去掉那条多出来的限制先把环在某一条边上剪开你会发现它变成了一条有 n 个点的链这 n 个点首尾不再相邻只剩下“内部相邻点不同色”的条件。一条 n 个点的链第一个点可以随便选有 m 种之后每个点只要避开前一个点的颜色都有 m - 1 种选择。所以链的总染色数是链方案数 m × (m - 1)^(n - 1)现在的问题是这些链方案里有多少个在把首尾接回去之后仍然合法显然只有“首尾两点颜色不同”的方案接成环后才满足相邻不同色的条件。换句话说合法的环染色数 链方案数 - 首尾同色的链方案数。麻烦的是“首尾同色”的链方案数怎么算。这里有个非常漂亮的观察如果一条链的首尾同色把这两个点合并成一个点得到的是一个有 n - 1 个点的环而且这个合并后的环本身一定合法——为什么因为首尾这两个点原本分别和它们内侧的相邻点颜色不同合并成同一个点后这个新点仍然区别于它两侧的邻点。反过来任意一个 n - 1 个点的合法环染色随便选一个点把它“拆开”成两个同色相邻点也就得到了一条首尾同色的 n 点链。这是一一对应。所以立刻得到递推关系f(n) m × (m - 1)^(n - 1) - f(n - 1)边界条件是 f(2) m × (m - 1)因为两个区域围成一个圈本质上只要求这两个区域不同色。这个一阶递推很好解。先猜一个形状再归纳验证令 f(n) (m - 1)^n (-1)^n (m - 1)。代入递推的右边m × (m - 1)^(n - 1) - [ (m - 1)^(n - 1) (-1)^(n - 1)(m - 1) ] (m - 1)^n - (-1)^(n - 1)(m - 1) (m - 1)^n (-1)^n (m - 1)完美闭环。递推法最大的价值在于它把环和链的关系讲清楚了也让 n1 和 n2 这种边界情况原形毕露后面避坑环节我还会再强调。2.2 容斥法那个最容易漏掉的修正项如果递推法靠的是“剪一刀”的几何直觉容斥法靠的就是纯粹的集合计数。这个方法在推导时有一个非常隐蔽的细节很多资料里都一笔带过但恰恰是最容易翻车的地方。把 n 个点看成编号 1 到 n边有 n 条边 1 连接点 1 和 2边 2 连接点 2 和 3依此类推边 n 连接点 n 和点 1。总方案数显然是 m^n因为每个点都有 m 种颜色可选。现在要扣除那些“至少有一条边的两端同色”的方案。定义事件 A_i 表示“第 i 条边的两个端点颜色相同”那么合法方案数就是所有 A_i 都不发生的方案数。容斥原理登场。对任意一组被选中的边集 S如果 |S| k 且 k n这些边在 n 个点的环上不可能构成闭合回路它们只会把 n 个点切成 n - k 个连通块每个连通块内部颜色必须一样。于是方案数为 m^(n - k)。从 k 条边中选出这个边集有 C(n, k) 种选法这里不需要纠结连通块长什么样因为每个连通块贡献一个自由颜色方案数只依赖于块数。但是当 k n 时也就是 n 条边全被选中情况就完全变了所有点连成一个大连通块整环只能是一种颜色方案数是 m而不是直觉上的 m^(n - n) m^0 1。这一个点的差异正是环形结构区别于普通图的本质特征。于是合法数 Σ_{k0}^{n-1} (-1)^k C(n,k) m^(n-k) (-1)^n × m把 k n 那一项补成统一形式再减掉修正项合法数 Σ_{k0}^{n} (-1)^k C(n,k) m^(n-k) - (-1)^n (-1)^n × m前面那一整坨正是二项式展开 (m - 1)^n。所以最终得到f(n) (m - 1)^n (-1)^n (m - 1)容斥法的好处是完全从“约束条件”出发不依赖首尾相接的几何直觉但它要求你对“选满所有边”这个特殊情况足够敏感。很多初学者在背公式的时候完全不知道这个修正项的存在自然不会明白为什么不是单纯等于 (m - 1)^n。2.3 两种推导方式怎么选递推法和容斥法不是互斥的它们恰好从两个角度揭示了同一个公式递推法告诉你这是环与链之间的转换关系容斥法告诉你这是“全选所有边”这个特殊集合带来的修正。实际使用中如果只是求方案数直接套公式或者用递推都行但如果题目换了个限制条件比如“某些边不允许同色”“某些点强制同色”这时候容斥法的框架往往更容易扩展因为它本质上就是在处理“强制条件集合”。我自己的习惯是先在草稿纸上用递推法快速写出公式再用容斥法核对一遍尤其是检查 k n 的修正项有没有漏。3. 别急着套公式先记牢这些特例与自查表3.1 最经典的例子正五边形的五顶点染色在数学竞赛里“环形染色问题”最常见的出场方式就是“正五边形的五个顶点用五种颜色染色相邻顶点不同色求方案数”。不要犹豫直接代公式m 5n 5。f(5) (5 - 1)^5 (-1)^5 × (5 - 1) 4^5 - 4 1024 - 4 10201020 种。这个数字看着不大但如果有人试图枚举会发现五个点的限制是环环相扣的枚举很容易重复或遗漏。公式的好处在这个时候体现得淋漓尽致。3.2 二色和三色的特殊情况很直观用两种颜色给环染色结果非常依赖 n 的奇偶性。m 2 时代入公式f(n) 1^n (-1)^n × 1 1 (-1)^n也就是说n 为偶数时方案数为 2n 为奇数时方案数为 0。这在直觉上完全成立两个颜色唯一可能的环形交替模式是 A-B-A-B...n 为偶数才能首尾接上而且只有两种颜色分配方式奇数是根本绕不回来的。同样三种颜色给三个区域染色也就是三角形的三个顶点两两相邻必须三色全不同方案数是 3 × 2 × 1 6。代入公式 m 3n 3f(3) 2^3 - 2 6完全吻合。这些特例不是用来背的是用来在考试或写代码时快速校验公式有没有用错的。3.3 小数据自查表我自己刷题时有个习惯套公式算完一定要先验一组小数据确认没有方向性错误。下面这张表列了 m 2、3、4 时前几个 n 的合法方案数建议读者自己拿公式也算一遍这个过程能帮你发现很多理解上的偏差。nm2m3m4226123062442188450302406266732以 m 4、n 4 为例公式给出 3^4 3 84。这个数可以这样交叉验证四个点围成一个四边形先按链算 4 × 3^3 108再减去首尾同色对应 f(3) 24得到 84。多一条验证路径少一分翻车风险。4. 代码实现三种写法的复杂度与适用场景4.1 O(n) 动态规划思路最直观如果不想背公式动态规划是最稳的保底方案。状态设计非常自然维护两个值一个是当前点和第一个点颜色相同的方案数 same一个是当前点和第一个点颜色不同的方案数 diff。初始时第一个点有 m 种颜色可选所以 same mdiff 0。每加入一个新点状态转移如下如果新点要和第一个点同色那它只有 1 种选择取第一个点的颜色而且要求上一个点和第一个点颜色不同否则相邻会撞色。所以新的 same 旧 diff。如果新点要和第一个点不同色分两种情况上一个点和第一个点同色那么新点不能和第一个点同色有 m - 1 种选择上一个点和第一个点不同色那么新点既要避开第一个点也要避开上一个点有 m - 2 种选择。所以新的 diff 旧 same × (m - 1) 旧 diff × (m - 2)。最终答案是处理完 n 个点后的 diff。def ring_color_dp(m, n): if n 1: return m same m diff 0 for _ in range(2, n 1): same, diff diff, same * (m - 1) diff * (m - 2) return diff这个 DP 的优点是很容易扩展到更复杂的约束比如加了“最多连续两个同色”之类的限制只需多开一维状态。缺点是当 n 达到 10^18 时O(n) 循环直接超时。4.2 O(log n) 矩阵快速幂应对超大 n一旦 n 的规模上亿DP 就不行了。好在上面那个递推是一个标准的线性递推可以写成 2×2 矩阵乘法。状态向量取 [same, diff]转移矩阵是M [[0, 1], [m - 1, m - 2]]因为same 0 × 旧same 1 × 旧diffdiff (m - 1) × 旧same (m - 2) × 旧diff初始向量 [m, 0]应用 M^(n-1) 后取第二维就是答案。def mat_mul(A, B, mod): return [ [(A[0][0] * B[0][0] A[0][1] * B[1][0]) % mod, (A[0][0] * B[0][1] A[0][1] * B[1][1]) % mod], [(A[1][0] * B[0][0] A[1][1] * B[1][0]) % mod, (A[1][0] * B[0][1] A[1][1] * B[1][1]) % mod], ] def mat_pow(M, p, mod): res [[1, 0], [0, 1]] while p: if p 1: res mat_mul(res, M, mod) M mat_mul(M, M, mod) p 1 return res def ring_color_matrix(m, n, mod): if n 1: return m % mod M [[0, 1], [(m - 1) % mod, (m - 2) % mod]] M mat_pow(M, n - 1, mod) return (M[1][0] * m) % mod矩阵快速幂的比赛标准姿势几乎所有支持快速幂的题目里都能用。不过说实话如果只是环形染色这一道题直接套公式快速幂就够了矩阵反而有点杀鸡用牛刀。它真正的价值在于当你需要把“环形染色”作为整个大算法的一个子模块时矩阵做法可以无缝嵌入。4.3 O(log n) 公式快速幂最简洁也最容易踩坑既然闭式公式已经写出来了为什么还要绕一圈直接快速幂算 (m - 1)^n再加上 (-1)^n 的修正项就行。def ring_color_formula(m, n, mod): if n 1: return m % mod ans pow(m - 1, n, mod) if n 1: ans (ans - (m - 1)) % mod else: ans (ans (m - 1)) % mod return ans这里有两个坑必须提醒。第一如果 m 和 n 都很大而且要对某个模数取模那么 (m - 1) 也要先取模再加或减不能把原始值带进去。第二如果要求输出的是非负整数Python 的%运算天然保证非负但 C 里要写成(ans mod) % mod的形状否则负数取模会给你意想不到的结果。公式写的短不代表它不重要恰恰相反它是三种写法里数值上最可控的也是我实际刷题时用得最多的。5. 变体与扩展从基础题到进阶题5.1 旋转和翻转要不要算同一种“环形染色问题”默认区域编号固定旋转或翻转后算不同方案。但现实场景里“圆环”经常没有那么强的编号感一条项链在手腕上旋转一下还是同一条一面圆桌在翻面之后摆法也一样。一旦题目要求“旋转或翻转视为同一种”基础公式就不能直接用了必须上 Burnside 引理。对称计数的一般流程是枚举置换群里的每个置换旋转 k 个位置、翻转轴等数出这个置换下保持不变的颜色方案数然后取平均值。对于环形染色旋转 k 个单位的不动点实际上等价于在一个更小的环上染色小环的规模是循环数因此仍然可以套用经典公式只是参数变了。翻转的不动点则需要单独讨论通常比旋转更麻烦。这类问题在“项链染色”“手镯染色”的经典组合计数题里出现频率很高以后遇到建议单独整理一篇这里点到为止。5.2 添加连续同色数量限制如果题目从“相邻不同色”改成“相邻最多允许两个同色不允许连续三个同色”公式就失效了因为约束不再只是边上的二元关系而是涉及长度为三的窗口。此时动态规划仍然适用只是状态要扩展一维记录当前点和第一个点颜色是否一致、以及当前已经连续了几个相同颜色。例如可以设 dp[i][j][c] 表示前 i 个点、第 i 个点与第一个点颜色关系为 j0 或 1、当前末尾连续同色长度为 c 的方案数。转移枚举新点颜色与上一个点是否相同即可。虽然状态数翻了常数倍但只要约束是“连续段的长度限制”这类 DP 就永远不会失效。这也是我建议你一定要理解 DP 解法而不是只会背公式的原因。5.3 必须 / 禁止使用某种颜色的计数再举一个常见变体用 m 种颜色给 n 个区域环形染色相邻不同色且规定颜色 1 至少出现一次。直接算“至少一次”常常让人头大但计算“一次都不出现”反而简单——把颜色 1 从色盘里删掉剩下 m - 1 种颜色继续做普通环形染色方案数是 f(n, m - 1)。于是答案就是总数减去这个“禁用颜色 1”的方案数至少出现一次 f(n, m) - f(n, m - 1)这类“强制出现”“禁止出现”的题型本质上是容斥思想在公式层面的应用。遇到更复杂的组合约束比如“颜色 1 和颜色 2 都必须出现”就用容斥原理逐层展开每一步都能套用经典公式。5.4 与色多项式的关系图论里有一个概念叫色多项式对一个图 G用 q 种颜色给顶点染色相邻顶点不同色记为 P(G, q)。对环图 C_n色多项式恰好就是P(C_n, q) (q - 1)^n (-1)^n (q - 1)所以你花费十几分钟推出来的环形染色公式在齐次坐标下其实就是环图的色多项式。理解了这一点遇到“若干个环拼在一起”的组合图时就不会觉得无从下手——很多情况下可以先拆成独立的环分别计数再用乘法原理合并。这也是为什么我说这是一个“入门简单、上限很高”的模型。6. 踩坑实录环形染色最容易翻车的四个地方6.1 n1 和 n2 的边界真的不是小事n 1 的时候环退化成单个点它和自己是同一点不存在“相邻区域颜色不同”的矛盾。如果你默认每个区域是独立的染色数应该是 m。但代入公式 (m - 1)^1 (-1)^1 (m - 1) 0显然是矛盾的。为什么因为递推法的“剪开”操作、容斥法的“选中全部 n 条边成环”描述都默认 n ≥ 2。处理 n 1 之前必须先看题目怎么定义“相邻”。如果题目没特别说明我会直接按特殊情况返回 m并在题解里明确标注。n 2 也好不到哪去两点的“环”其实只有一条边公式给的是 m(m - 1)但如果题目把两个区域看得更复杂需要小心读题。6.2 容斥全选边集时m^0 是个大坑我在 2.2 节特别强调了 k n 时的修正项。很多人第一次自己推容斥都会自然地写出Σ_{k0}^{n} (-1)^k C(n,k) m^(n-k)然后得意洋洋收工结果发现少了一项 (-1)^n (m - 1)。原因就在于把“选满所有 n 条边”理解成了“n 个连通块各 1 种颜色”但n条边全选后实际是 1 个连通块m 种颜色。这种错误极其隐蔽因为你对着二项式展开检查时会觉得每一步都顺理成章。所以我建议在推导容斥时把 k n 和 k n 分开写最后再合并。6.3 取模运算里负数处理不当直接错算法题里常见的模数是 10^9 7公式里的 (-1)^n 修正项很容易导致中间结果出现负数。C 里可以直接这样写long long ans mod_pow(m - 1, n, MOD); long long extra (m - 1) % MOD; if (n 1) ans (ans - extra MOD) % MOD; else ans (ans extra) % MOD;多写一个MOD能省下无数个晚上的排查时间。我见过太多次因为负取模导致 WA 到怀疑人生的案例这不是数学问题是语言细节。6.4 先确认“区域是否编号”再决定用哪个公式最后这个是审题层面的坑。同样一句话“把 n 个点围成一圈染色”如果题目说“圆形排列”“项链”大概率要考虑旋转等价如果题目说“正 n 边形的顶点依次编号”那就是标准的编号环。前者需要 Burnside后者才是本文公式的直接适用范围。我建议拿到题先圈出关键词出现“编号”“依次”“固定位置”直接套公式出现“旋转”“翻转”“等价”立刻切到置换群计数框架。这个模型本身不难但它像一面镜子把你对“环的对称性”理解得够不够透彻照得清清楚楚。我自己的体会是与其机械记公式不如把递推法那“剪一刀”的思路刻在脑子里遇到再复杂的环形变体先剪成链再一步步加限制回来基本不会走偏。