레이팅 미적용때는 \(3000\)년, 베시는 우주에 간 최초의 소가 되었다! 별들 사이를 여행하던 중, 베시는 \(1\)부터 \(N\)까지 번호가 매겨진 \(N\)(\(2 \leq N \leq 5 \cdot 10^5\))개의 점이 있는 수직선을 발견했다. 모든 점은 처음에 흰색으로 칠해져 있다. 베시는 다음 연산을 원하는 만큼 수행할 수 있다.
- 수직선 위의 위치 \(i\)와 양의 정수 \(x\)를 선택한다. 그런 다음 구간 \([i, i + x - 1]\)의 모든 점을 빨간색으로, 구간 \([i + x, i + 2x - 1]\)의 모든 점을 파란색으로 칠한다. 선택한 모든 구간은 서로 겹치지 않아야 한다 (즉, \([i, i + 2x - 1]\)의 어떤 점도 이미 빨간색이나 파란색으로 칠해져 있어서는 안 된다). 전체 구간은 수직선 안에 완전히 들어가야 한다 (즉, \(1 \leq i \leq i + 2x - 1 \leq N\)).
농부 존은 베시에게 문자 \(R\), \(B\), \(X\)로 이루어진 길이 \(N\)의 문자열 \(s\)를 준다. 이 문자열은 각 점에 대한 농부 존의 색 선호를 나타낸다: \(s_i=R\)이면 \(i\)번째 점은 빨간색으로 칠해져야 하고, \(s_i = B\)이면 \(i\)번째 점은 파란색으로 칠해져야 하며, \(s_i = X\)이면 \(i\)번째 점의 색에는 제약이 없다.
농부 존의 선호를 만족하도록 수직선을 칠하는 서로 다른 방법의 수를 세는 것을 베시가 도와주자. 대응하는 점 중 색이 다른 점이 하나라도 있으면 두 색칠은 서로 다른 것이다. 답이 클 수 있으므로 \(10^9+7\)로 나눈 나머지를 출력한다.
문제 제공: Chongtian Ma, Alex Liang
배점
- 입력 4: \(N\le 500\)
- 입력 5-6: \(N\le 10^4\)
- 입력 7-13: \(s\)에서 최대 \(100\)개를 제외한 모든 문자가 \(X\)이다.
- 입력 14-23: 추가 제약 없음
문제 제공: Chongtian Ma, Alex Liang
첫째 줄에 정수 \(N\)이 주어진다.
다음 줄에 문자열 \(s\)가 주어진다.
농부 존의 선호를 만족하도록 수직선을 칠하는 서로 다른 방법의 수를 \(10^9+7\)로 나눈 나머지를 출력한다.
6
RXXXXB5Bessie 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\).
6
XXRBXX6The six colorings are \(WWRBWW\), \(WWRBRB\), \(WRRBBW\), \(RBRBWW\), \(RBRBRB\), and \(RRRBBB\).
12
XBXXXXRXRBXX18riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > December > Gold