取自 2026.2.27 数学课。
考虑一个固定的 \(n\) 等分的圆，有 \(m\) 种颜色，每一个小扇形填一种，相邻扇形颜色不能相同，求总方案数。
Sol 1
设 \(f(i,j),g(i,j)\) 为第 i 个扇形填第 j 个颜色的方案数，有转移：
\[f(i,j)=\sum_{1 \leq k \leq m,k \ne j} f(i,j),
\]
\[g(i,j)=\sum_{1 \leq k \leq m,k \ne j} g(i,j)
\]
初始 \(g(1,1)=1,\forall i \in [1,m],f(1,i)=1\)，答案即 \(m\times( f(n,1)-g(n,1))\)。
Sol 2
发现状态有大量数重复，考虑简化元。
设 \(a_k,u_k,v_k\) 分别为 \(n=k\) 时的答案，从某一颜色出发走了 \(k\) 个格子（不含起始格）回到 / 没回到初始颜色的方案数。
\(n=1\) 的情况是平凡的， \(a_n=m\)，下考虑 \(n \geq 2\) 的情况。
不难得到：
\[a_n=m(m-1)^{n-1}-m \times u_{n-1},
\]
\[u_n=(m-1)v_{n-1},
\]
\[v_n=(m-2)v_{n-1}+u_{n-1}
\]
消去 \(v\)，得到：
\[u_{n+1}=(m-2)u_{n}+(m-1)u_{n-1},n \geq 1
\]
即：
\[u_{n+2}=(m-2)u_{n+1}+(m-1)u_{n},n \geq 0
\]
边界 \(u_0=1,u_1=0\)。
到这里我们可以使用矩阵乘法，在 \(O(\log n+m^2)\) 的复杂度内解决这个问题。
Sol 3
考虑使用 gf。
设 $$F(x)=\sum_{k \geq 0} u_kx^k$$
因为 \(u_0=1,u_1=0\)，所以有：
\[\frac{F(x)-1}{x^2}=(m-2) \times \frac{F(x)-1}{x}+(m-1)\times F(x)
\]
解得
\[F(x)=\frac{1-(m-2)x}{1-x(m-2)-x^2(m-1)}
\]
发现这个分母是可以因式分解的，联想到斐波那契数列的部分分式分解，设：
\[F(x)=\frac{A}{1-ax}+\frac{B}{1-bx}=\frac{A+B-(Ab+aB)x}{(1-ax)(1-bx)}
\]
对比系数得：
\[\left\{\begin{matrix} A+B=1\\ (-1) \cdot A+(m-1)\cdot B=m-2\\ a=m-1\\ b=-1\end{matrix}\right.\]
解得
\[F(x)=\frac{1}{m} \times \frac{1}{1-(m-1)x}+\frac{m-1}{m} \times \frac{1}{1-(-x)}
\]
利用广义二项式定理展开得
\[[x^n]F(x)=\frac{1}{m} \times (m-1)^k+\frac{m-1}{m} \times (-1)^k
\]
即 $$u_k=\frac{1}{m} \times (m-1)^k+\frac{m-1}{m} \times (-1)^k,k \geq 0$$
代入 \(a_n=m(m-1)^{n-1}-m \times u_{n-1},n \geq 1\)，得到：
\[a_n=\left\{\begin{matrix} 1,n=1\\(m-1)^n+(-1)^n (m-1),n \geq 2
\end{matrix}\right.\]
这便给出了这个问题的通解。