페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4155

Help Yourself 2s 512MB

문제

정수 N개의 닫힌 구간이 1차원 직선 위에 주어진다.
i번째 구간은 [l_i, r_i] 이며, 이는 l_i \le x \le r_il 를 만족하는 모든 실수 x를 포함한다.

하나의 구간 집합 S에 대해, 그 합집합을 S에 속한 구간들 중 적어도 하나에 포함되는 모든 실수들의 집합이라고 하자.
이때, 합집합이 이루는 연결된 구간(connected components) 의 개수를 c(S)라 하자.

정수 K가 주어질 때, 집합 S의 복잡도를 \text{complexity}(S) = \big(c(S)\big)^K로 정의한다. (공집합의 경우 c(\varnothing) = 0 이다.)

모든 2^N개의 부분집합 S에 대해 \text{complexity}(S)의 합을 계산하고, 그 값을 10^9 + 7 로 나눈 나머지를 구하여라.


입력

첫 줄에 두 정수 N, K가 주어진다.
다음 N개의 줄의 iii번째 줄에는 두 정수 l_i, r_i가 주어지며, 구간 [l_i, r_i]를 나타낸다.


출력

모든 부분집합 S에 대해 \text{complexity}(S)의 합을 구하고, 그 값을 10^9 + 7 로 나눈 나머지를 출력한다.


예제 

3 2
1 6
2 3
4 5
10

선분 집합의 복잡도는 “합집합이 이루는 연결 구간의 개수의 제곱(K=2이므로 제곱)”이다.
공집합의 복잡도는 0^2 = 0 이고, 예제 설명에서는 빈 집합을 제외한 모든 부분집합의 복잡도를 나열하고 있다.

선분을 편의상
A = [1, 6], B = [2, 3], C = [4, 5] 라고 하자.

  • {A} → 합집합은 [1, 6] 한 구간 → 연결 구간 1개 → 복잡도 1^2 = 1

  • {B} → [2, 3] → 1개 → 1

  • {C} → [4, 5] → 1개 → 1

  • {A, B} → [1, 6]과 [2, 3]의 합집합은 여전히 [1, 6] 하나 → 1개 → 1

  • {A, C} → [1, 6]과 [4, 5]의 합집합도 [1, 6] 하나 → 1개 → 1

  • {B, C} → [2,3] ∪ [4,5] 는 서로 떨어진 두 구간 → 연결 구간 2개 → 복잡도 2^2 = 4

  • {A, B, C} → 세 선분의 합집합은 [1, 6] 하나 → 1개 → 1

따라서 (공집합을 제외한) 복잡도의 합은
1 + 1 + 1 + 1 + 1 + 4 + 1 = 10 이고, 정답은 10이다.


출처

USACO 2020 February Platinum
로그인해야 코드를 작성할 수 있어요.