感觉这题顺推下来并不难，关键是对过程中的一些 case 如何统一起来，从而减少讨论工作量。 结论比较有意思，但整道题过程较繁琐。也是一道好题。

先考虑对于结果序列 ，我们能不能将其染成。

首先对于 中为白色的部分，其两边是独立的子问题。可以分开。

先考虑 没有白色的情况，因为操作都是区间覆盖，所以 中的相等连续段可以缩在一起。此时 一定是 RB 交错的形式。注意到如果首尾为 B，在首尾添加一个 R 没有影响（只需要让第一次 R 操作"扩大"一下即可）。所以，每一种只有红蓝色的结果序列，都能被化归到 的形式。

那最后的 也可以看作若干段 与中间一些 拼成的串。设共有 段，每段长度为 。（下文的“长度” 都定义为其中 的个数）

我们考虑一个长度为 的段需要什么样的操作将其染成。

时，只需一个操作 。 时，需要两个操作 。 时，操作序列 与 都是可行的。

用数学归纳法可以得到，当 时，只要操作序列前两个是 ，后面接 个任意字符就行。显然这也是充要条件。

此时我们发现 与 要分开考虑，枚举 表示 的个数。那我们需要将 串分为 个 与 个满足那些段的操作序列。

那么在原串中找到最前面的 个 。在最前面的 个 后面分别找到最前的一个 与其配对。将这些字符标记为已经使用。显然我们找到的这些作为那 个操作序列的开头一定是不劣的。

设 表示第 对 后面的空余字符数。我们将 与 从小到大排序，对 的限制就是 。

考虑 DP 排序后的 数组，设 表示当前到第 位，当前 ，。转移枚举下一个 相等段的长度 与值 ：。(乘组合数是因为我们 DP 的是排序后的 数组，要乘组合数还原成排序前的)。

容易用前缀和优化做到 。

但我们还要解决一个问题，现在我们考虑的 都对应的是原序列的一段 ，怎么将我们考虑的东西还原到原序列上。

先考虑单个 的部分，它恰好有 段，但是首尾两段可能为空，那么我们在这个部分的两端加入两个虚拟的 ，此时这两段不可能为空，但序列长度变成 。这一个段与两边的两个 一共会形成 个分界点，但又是首尾有例外，所以我们在原序列首尾各加一个 ，此时序列长度为 ，一共有 个分界点，那么将缩段后的序列对应到原序列的方案数就是 。

综上所述，我们枚举 ，表示总的 RB 段数以及单个 R 的段数，然后找到最前的 个 与对应最前的 个 ，接着跑那个 DP，最后枚举 的值统计答案。总时间复杂度上界为 ，但显然跑不满，很轻松地过了 。