注意到一个事情，当这个序列是完美序列时，序列两头的颜色是相同的，故所有的完美序列都是这样一层一层的套上去的层次结构。

因此对于 $f_n$，我们只需在长度小于 $n$ 的序列外套一层其他颜色。假设从长度为 $f_i$ 外套一层长 $n-i$ 的其他颜色，有 $n - i - 1$ 种套法，并且其他颜色有 $k-1$ 种选法。这可以自然的导出转移方程（觉得难以理解的，可以在 DP 中增加一维层数）

直接做的复杂度是 $O(n ^ 2)$，可以用前缀和优化转移的过程，复杂度为 $O (n)$。当然也可以使用快速幂、整式递推等科技优化到 $O(\log n)$，可以自行尝试。

这里是代码（写法一）

这里是代码（写法二）