环形染色问题

基本模型:

一个环形区域有n小块，有m种染料，给这些小块染色，其中相邻的小块颜色不相同，问有多少种染色方案。

问题分析:

1.将n个小块进行编号1~n。

2.分析每块的上色方案，第一块有m种方案，第二块有m-1种方案，第三块也有m-1种方案，一直到第n块都是m-1种方案，因此一共有m 方案。

3.而这m 方案又分为两种情况:
(1)第n块与第1块颜色不同。
我们可以设i块的方案数为 ，那显然这种情况下的方案数就是 ;
(2)第n块与第1块颜色相同。
这种情况下如果看成n块显然就不成立，因此我们可以把第n块和1块合并，把它看成n-1块，也就是这样
因此这种情况下的方案数就是 。
综合这两种情况，可以得出递推关系式 。

4.根据递推关系式，

因此有，
;
……
;

一层一层代入可以得到:

又由于 ，

因此

公式总结:

题目举例:

Yuanyuan Long and His Ballons:

问题传送门：https://ac.nowcoder.com/acm/problem/14584
题解传送门：https://blog.nowcoder.net/n/9dc81f8e17eb4e8bb218fafee0d65ac0