Interstellar Intervals

题目描述

现在是 $3000$ 年，Bessie 成为了第一头进入太空的奶牛！在她穿梭于群星之间的旅程中，她发现了一条数轴，上面有 $N$（$2 \leq N \leq 5 \cdot 10^5$）个点，编号从 $1$ 到 $N$。所有点最初都被染成白色。她可以执行以下操作任意多次。

选择数轴上的一个位置 $i$ 和一个正整数 $x$。 然后，将区间 $[i, i + x - 1]$ 中的所有点染成红色，将区间 $[i + x, i + 2x - 1]$ 中的所有点染成蓝色。所有被选择的区间必须两两不相交（即 $[i, i + 2x - 1]$ 中的任何点都不能已经被染成红色或蓝色）。整个区间也必须完全落在数轴范围内（即 $1 \leq i \leq i + 2x - 1 \leq N$）。

Farmer John 给了 Bessie 一个长度为 $N$ 的字符串 $s$，由字符 $R$、$B$ 和 $X$ 组成。该字符串表示 Farmer John 对每个点的颜色偏好：$s_i=R$ 表示第 $i$ 个点必须被染成红色，$s_i = B$ 表示第 $i$ 个点必须被染成蓝色，$s_i = X$ 表示对第 $i$ 个点的颜色没有约束。

请帮助 Bessie 统计在满足 Farmer John 偏好的前提下，数轴可以被染色的不同方案数。若存在至少一个对应点的颜色不同，则认为两种染色方案不同。由于答案可能很大，请输出对 $10^9+7$ 取模后的结果。

输入格式

第一行包含一个整数 $N$。 下一行包含字符串 $s$。

输出格式

输出满足 Farmer John 偏好要求的不同染色方案数，并对 $10^9+7$ 取模。

6
RXXXXB

5

6
XXRBXX

6

12
XBXXXXRXRBXX

18

提示

Bessie 可以选择 $i=1,x=1$（即将第 $1$ 个点染红、第 $2$ 个点染蓝）以及 $i=3,x=2$（即将第 $3,4$ 个点染红、第 $5,6$ 个点染蓝），从而得到染色结果 $RBRRBB$。 其他染色结果为 $RRBBRB$、$RBWWRB$、$RRRBBB$ 和 $RBRBRB$。

这六种染色结果为 $WWRBWW$、$WWRBRB$、$WRRBBW$、$RBRBWW$、$RBRBRB$ 和 $RRRBBB$。

计分（SCORING）： Input 4: $N\le 500$ Inputs 5-6: $N\le 10^4$ Inputs 7-13: 字符串 $s$ 中除至多 $100$ 个字符外，其余均为 $X$。 Inputs 14-23: 无额外限制 题目贡献者：Chongtian Ma, Alex Liang

标签: USACO|2024|Gold

来源

USACO|2024|Gold