*2600
核心：每种颜色只会染色一次。染色前的区间必定是单种颜色。
把颜色相同的段先缩起来。因为他们一定会同时被选。
此时 m 还是很大，可以构造序列 [1...n] 一直重复。
考虑另外一个性质，一次操作类似 ODT 分析，最多会把边界位置加上 \(a_i\neq a_{i+1}\) 的情况。所以这样的位置上界为 \(2n\)。
所以如果缩完点后的序列长度大于了 \(2n\) 一定不合法。现在我们有 \(m\le 2n=10^3\)。非常好啊！
时限 6s 并根据 F1，我们进行区间 dp。优先考虑最先染的颜色位置集合 \(i_1...i_k\)。
最先进行的操作是覆盖 \([l,r]\) 满足 \(l\le i_1, r\ge i_k\)。并且操作完之后发现变成了很多个子问题（因为染色要保证区间颜色相同，所以不能跨越，还有原因是跨越染之后那个跨越的点就变颜色了）。转移：
\[dp(L,R)=\sum_{l\le i_1,r\ge i_k}dp(L,l-1)dp(l,i_1-1)dp(i_k+1,r)dp(r+1,R) \prod_{1\le p<k}dp(i_p+1,i_{p+1}-1) \]后面 prod 的部分容易快速得到，前面和 \(l,r\) 有关，考虑分成 \([l,i_1),(i_k,r]\) 两个段，分别算 sum，最后乘起来即可。转移复杂度 \(O(m)\)。
复杂度达到了惊人的 \(10^9\)，但是这是 CF 并且给了 6s。应该可以通过。
标签：le,颜色,染色,ge,CF1178F2,2n,dp From： https://www.cnblogs.com/LCat90/p/18546188