菜王的 blog

首先可以想到设 $f_i$ 为长度为 $i$ 的网格的个数。

然后考虑转移，具体考虑第 $i$ 个格子染成什么颜色。可以分成两种情况：

• 第 $i$ 个格子前 $k - 1$ 个格子颜色相同。这样当前格可以染成任意颜色。

• 否则，前 $k - 1$ 个格子里共出现过两种颜色。这样当前格只能在这两种颜色之中选择。

显然，每一个长度为 $i - k + 1$ 的网格都与一个长度为 $i - 1$ 且后 $k - 1$ 个格子颜色相同的网格形成双射，因为我们可以把前者的最后一个格子再复制 $k - 2$ 次接在后面形成后者，且满足要求。所以后者的方案数即为 $f_{i - k + 1}$。

而容斥可得长度为 $i - 1$ 且后 $k - 1$ 个格子里共出现过两种颜色的网格个数即为 $f_{i - 1} - f_{i - k + 1}$。

可得转移方程：

$f_{i} = 2(f_{i - 1} - f_{i - k + 1}) + c \times f_{i - k + 1}$

整理后可得

$f_{i} = 2f_{i - 1} + (c - 2)f_{i - k + 1}$

然后考虑 $f_{1 \sim k}$ 的初始化。

$f_i$ 其实就是在 $c$ 种颜色中选择两种颜色，然后用这两种颜色染 $i$ 个格子的方案数，$\binom c2 2^i$。但是这样会计重，只使用一种颜色的方案会算 $c - 1$ 次，所以得

$f_{i} = \binom c2 2^i - c(c - 2) \ (i \le k)$

答案为 $f_{n}$。时间复杂度为 $O(n)$。

可以发现，虽然方程中出现了 $\binom c2, c - 2$ 这样的东西，但是把 $c = 1$ 的情况代入进去是完全没有问题的。