problem
有一个环，环上有 n 个格。先要给这 n 个格子染上 m 种颜色。每个格子只能染一种颜色，相邻两个格子颜色不同。问方案个数。
sol
我们先把他当链做：这样有 m(m−1)n−1 种做法。
在变成环，分类讨论：
-
1 和 n 相同这样就有 fn−1 种方案
-
反之，为 fn 种做法
所以 fn+fn−1=m(m−1)n−1 。
还可以化：
fn+fn−1=m(m−1)n−1=(m−1+1)(m−1)n−1=(m−1)n+(m−1)n−1
移项，得
fn−(m−1)n=−(fn−1−(m−1)n−1)
我们令 bn=fn−(m−1)n，你会发现
bn−1bn=−1，所以 b 是个等比数列。
当 n=2 时，显然，f2=m(m−1)，则
b2=f2−(m−1)2=m(m−1)−(m−1)2=m−1
所以 bn=b2×(−1)n−2=(−1)n×(m−1)
又因为 fn=bn+(m−1)n，
所以 fn=(m−1)n+(−1)n×(m−1)。