首先不难发现，所有的完美序列，前后两端的颜色是相同的。完美序列的前缀连续相同颜色的个数和后缀连续相同颜色的个数之和大于等于3。类似括号序列一样，我们可以发现在完美序列的两端加三个以上的相同颜色的珠子依旧是完美序列（两端至少加一个）。

假定 xxxxxx 是完美序列，那么加上三个相同颜色的珠子 11xxxxxx1, 1xxxxxx11也是完美序列。加上四个相同的数字则会得到 2xxxxx222，22xxxxx22，222xxxxx2。显然，得到的完美序列两端同样保证了颜色相同。

可以得到转移方程

$$f(n) = \sum_{i=1}^{n - 3}f(i) * (n - i - 1) * (k - 1) $$

直接做的复杂度是 $O(n ^ 2)$，可以用前缀和优化转移的过程，复杂度为 $O (n)$。

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

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

$$f_n = \sum_{i=1}^{n-3} (n-i-1) (k-1)f_i$$

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

这里是代码（写法一）

这里是代码（写法二）