首先不难发现，所有的完美序列，前后两端的颜色是相同的。完美序列的前缀连续相同颜色的个数和后缀连续相同颜色的个数之和大于等于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)$。