设 \(f_{i, j}\) 为前 \(i\) 个最后以 \(j\) 结尾的方案数。
那么考虑转移，比较经典且我之前做过的例子是在 DP 转移过程中容斥，考虑将所有可能目前方案数减去最后恰好有 \(len\) 个重复元素的方案数，转移是比较经典的。
好的兄弟们现在你会做 \(k \le 100\) 的情况了，现在我们来研究一下 \(k \le 10^5\) 的情况。
考虑设 \(g_i = \sum f_{i, j}\)，那么根据容斥式子有：
\[f_{i, j} = g_{i - 1} - g_{i - len} + f_{i - len, j} = g_{i - 1} - g_{i - len} + g_{i - len - 1} - g_{i - 2len} + ... + g_{i - (k - 1)len - 1} - g_{i - klen} + g_{i - klen - 1}
\]
这是 \(f\) 的展开形式，也就是说 \(f\) 可以通过 \(g\) 表示出来，对于每个 \(j\)，\(k\) 的值可能不一样。
那么我们令 \(s_i = s_i + s_{i - len} + ...\)，那么有：
\[f_{i, j} = s_{i - 1} - s_{i - (k + 1)len - 1} - ( s_{i - len} - s_{i - (k + 1)len} )
\]
但问题是现在对于不同的 \(j\)，这个表达式还是本质不同的，我们没有办法简单维护。
注意到 \(k\) 的含义是向左走 \(len\)，第一次走到不是 \(j\) 的位置 \(k\)，由于一个位置实际上只会有一个颜色与其相同，其实 \(k\) 的取值只会有两个不同。
根据这个意义就可以很简单的 \(O(n)\) 维护了。