浅谈环染色问题

時空 · 2025-07-20 21:49:40 · 算法·理论

写在前面

模拟赛被这玩意创飞了。学习一下。

问题

长度为 n 的环型序列，用 m 种颜色进行染色，要求序列相邻的元素颜色不同，求方案数。

解决方案

下文中，记 col_x 表示 x 号元素的颜色。同时记 a_i 表示前 i 个元素染色的方案数。显然有边界 a_1 = 0，a_2 = m(m-1)。

考虑进行递推。分讨第 i 个元素的情况。

综上，a_i = (m-1)a_{i-2} + (m-2)a_{i-1}。\ 当 n 极大时，使用矩阵加速递推即可。

事实上，这个式子是可以求通项的。但是需要使用高中数学。\ 由于笔者是初中生，这里不进行扩展。感兴趣的读者可以自行搜集资料了解。