#PU1450. USACO 2024 December Contest, Gold — Problem 2. Interstellar Intervals

    ID: 1302 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec24来源:usaco.orgscoring:equal_test_cases线段树动态规划

USACO 2024 December Contest, Gold — Problem 2. Interstellar Intervals

USACO 2024 December Contest, Gold — Problem 2. Interstellar Intervals

题目描述

It's the year 30003000, and Bessie became the first cow in space! During her journey between the stars, she found a number line with NN (2≤N≤5⋅1052 \leq N \leq 5 \cdot 10^5) points, numbered from 11 to NN. All points are initially colored white. She can perform the following operation any number of times. Choose a position ii within the number line and a positive integer xx. Then, color all the points in the interval [i,i+x−1][i, i + x - 1] red and all points in [i+x,i+2x−1][i + x, i + 2x - 1] blue. All chosen intervals must be disjoint (i.e. no points in [i,i+2x−1][i, i + 2x - 1] can be already colored red or blue). The entire interval must also fall within the number line (i.e. 1≤i≤i+2x−1≤N1 \leq i \leq i + 2x - 1 \leq N). Farmer John gives Bessie a string ss of length NN consisting of characters RR, BB, and XX. The string represents Farmer John's color preferences for each point: si=Rs_i=R means the ii'th point must be colored red, si=Bs_i = B means the ii'th point must be colored blue, and si=Xs_i = X means there is no constraint on the color for the ii'th point. Help Bessie count the number of distinct ways for the number line to be colored while satisfying Farmer John's preferences. Two colorings are different if there is at least one corresponding point with a different color. Because the answer may be large, output it modulo 109+710^9+7.

输入格式

The first line contains an integer NN. The following line contains string ss.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

6
RXXXXB
5
Bessie can choose $i=1,x=1$ (i.e. color point $1$ red and point $2$ blue) and
$i=3,x=2$ (i.e. color points $3,4$ red and points $5,6$ blue) to produce the
coloring $RBRRBB$.
The other colorings are $RRBBRB$, $RBWWRB$, $RRRBBB$, and
$RBRBRB$.

样例 2

6
XXRBXX
6
The six colorings are $WWRBWW$, $WWRBRB$, $WRRBBW$, $RBRBWW$, $RBRBRB$, and $RRRBBB$.

样例 3

12
XBXXXXRXRBXX
18