智商低还种花
题目翻译
将 m 种不同花放在 n 个点围成的环里，需保证相邻的点不是同一种花，求方案数
解题思路
a.我们先假设 n 个点形成了一条链而不是一个环，那么方案数为 m(m - 1)^{n - 1}
b.显然 n 个点形成了一个环的方案数只需要 m(m - 1)^{n - 1} 再减去最后一个位置和第一个位置重复的个数就行了
c.分类讨论
\hspace{0.5cm} 1.若倒数第二个位置和第一个位置选择的花是同一种，则倒数第一个位置一定和第一个位置选择的花不是同一种
\hspace{0.5cm} 2.当倒数第二个位置和第一个位置选择的花不是同一种，倒数第二个位置和第一个位置的每一种选择的花都不是同一种，最后一个位置都会存在和第一个位置选择的花是同一种的情况被计算在 m(m - 1)^{n - 1} 种方案中
d.所以 n 个点形成了一个环的方案数就是 m(m - 1)^{n - 1} 减去倒数第二个位置和第一个位置不相同的方案数
e.设 f_n 表示有 n 个位置时的方案数
\hspace{0.5cm} 递推方程为 f_n = m(m - 1)^{n - 1} - f_{n - 1}
\hspace{0.5cm} 特定的， f_1 = m ， f_2 = m(m - 1)
线性是很优秀，但是因为 0 < n \le 10^{18} 还是会 T 飞
所以用等比数列求和优化，变成 f_n = (m - 1)^n + (m - 1)(-1)^n ， O(log_2n) T 不了了