레이팅 미적용베시는 1차원 수직선 위의 선분 \(N\)개(\(1\le N\le 10^5\))를 받았다. \(i\)번째 선분은 \(l_i\le x\le r_i\)인 모든 실수 \(x\)를 포함한다.
선분 집합의 합집합을, 적어도 하나의 선분에 포함되는 모든 \(x\)의 집합으로 정의한다. 선분 집합의 복잡도를, 그 합집합에 나타나는 연결된 영역의 개수로 정의한다.
베시는 주어진 \(N\)개의 선분 집합의 모든 \(2^N\)개의 부분집합에 대한 복잡도의 합을 \(10^9+7\)로 나눈 나머지로 계산하고 싶다.
보통은 베시를 돕는 것이 여러분의 일이다. 하지만 이번에는 여러분이 베시이고, 도와줄 사람이 아무도 없다. 스스로를 도와라!
문제 제공: Benjamin Qi
배점
- 테스트 케이스 2-3은 \(N\le 16\)을 만족한다.
- 테스트 케이스 4-7은 \(N\le 1000\)을 만족한다.
- 테스트 케이스 8-12는 추가 제약이 없다.
문제 제공: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄 각각에 두 정수 \(l_i\)와 \(r_i\)가 주어진다. \(l_i< r_i\)이고, 모든 \(l_i,r_i\)는 \(1 \ldots 2N\) 범위의 서로 다른 정수임이 보장된다.
답을 \(10^9+7\)로 나눈 나머지를 출력한다.
help.in · 출력을 쓸 파일 help.out3
1 6
2 3
4 58The complexity of each nonempty subset is written below.
$$ \{[1,6]\} \implies 1, \{[2,3]\} \implies 1, \{[4,5]\} \implies 1 $$
$$ \{[1,6],[2,3]\} \implies 1, \{[1,6],[4,5]\} \implies 1, \{[2,3],[4,5]\} \implies 2 $$
$$ \{[1,6],[2,3],[4,5]\} \implies 1 $$
The answer is \(1+1+1+1+1+2+1=8\).
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > February > Gold