浅谈环染色问题

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

长度为

n

的环型序列，用

m

种颜色进行染色，要求序列相邻的元素颜色不同，求方案数。

下文中，记

col_x

表示

x

号元素的颜色。同时记

a_i

表示前

i

个元素染色的方案数。显然有边界

a_1 = 0

，

a_2 = m(m-1)

。

考虑进行递推。分讨第

i

个元素的情况。

$col_1 = col_{i-1}$ 。此时 $col_i$ 的染色方案数为 $m - 1$ 。然后你发现由于 $col_i = col_{i-1}$ 的元素颜色相同，所以可以考虑把它们看作一个整体，那么元素 $1 \sim i-2$ 又成为了一个环！那么方案数就是 $a_{i-2}$ 了。所以此时的染色方案数为 $(m - 1)a_{i-2}$ 。
$col_1 \ne col_{i-1}$ 。此时 $col_i$ 的染色方案数为 $m-2$ 。类似地，由于 $col_1 \ne col_{i-1}$ ，元素 $1 \sim i-1$ 成为了一个环。那么方案数就是 $(m-2)a_{i-1}$ 。

综上，

a_i = (m-1)a_{i-2} + (m-2)a_{i-1}

。
当

n

极大时，使用矩阵加速递推即可。

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

文章操作