레이팅 미적용소 캠프에 \(1\dots N\)으로 번호가 붙은 \(N\) (\(1\le N \leq 10^6\))마리의 소가 있다. 각 소는 캠프 참가자이거나 코치이다.
소들 중 공집합이 아닌 부분집합이 현장 학습에 참가하도록 선발된다. \(i\)번째 소가 선발되면, 그 소는 수직선 위의 위치 \(p_i\) (\(0\le p_i \leq 10^9\))로 이동하며, 배열 \(p\)는 순증가한다.
소들의 공집합이 아닌 부분집합이 "좋은" 부분집합이라는 것은, 선발된 모든 참가자에 대해 왼쪽으로 \(D\) (\(0\le D\le 10^9\)) 단위 이내(경계 포함)에 선발된 코치가 존재한다는 것이다. 좋은 부분집합의 개수를 \(10^9+7\)로 나눈 나머지를 구하라.
Problem credits: Agastya Goel, Eva Zhu, and Benjamin Qi
SCORING
- 입력 3: \(N=20\)
- 입력 4: \(D=0\)
- 입력 5-8: \(N\le 5000\)
- 입력 9-16: 추가 제약 없음.
Problem credits: Agastya Goel, Eva Zhu, and Benjamin Qi
첫째 줄에 두 정수 \(N\)과 \(D\)가 주어진다.
다음 \(N\)개의 줄에 각각 두 정수 \(p_i\)와 \(o_i\)가 주어진다. \(p_i\)는 \(i\)번째 소가 이동할 위치를 나타낸다. \(o_i=1\)이면 \(i\)번째 소가 코치이고, \(o_i=0\)이면 \(i\)번째 소가 참가자이다.
\(p_i\)는 순증가하는 순서로 주어짐이 보장된다.
좋은 부분집합의 개수를 \(10^9 + 7\)로 나눈 나머지를 출력한다.
6 1
3 1
4 0
6 1
7 1
9 0
10 011The last two campers can never be selected. All other nonempty subsets work as
long as if cow \(2\) is selected, then cow \(1\) is also selected.
20 24
3 0
14 0
17 1
20 0
21 0
22 1
28 0
30 0
32 0
33 1
38 0
40 0
52 0
58 0
73 0
75 0
77 1
81 1
84 1
97 013094riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > First Contest > Gold