레이팅 미적용베시는 소 화학(cow-mistry) 숙제를 미루고 미루다가 이제 당신의 도움이 필요하게 되었다! 베시는 서로 다른 세 가지 소 화학물질(cow-michal)의 혼합물을 만들어야 한다. 하지만 훌륭한 소라면 누구나 알듯이, 일부 소 화학물질은 서로 섞으면 폭발을 일으키므로 섞을 수 없다. 구체적으로, 라벨이 \(a\)와 \(b\)인 두 소 화학물질은 \(a \oplus b \le K\)(\(1 \le K \le 10^9\))일 때에만 같은 혼합물에 함께 들어갈 수 있다.
참고: 여기서 \(a\oplus b\)는 음이 아닌 정수 \(a\)와 \(b\)의 "비트 단위 배타적 논리합(XOR)"을 나타낸다. 이 연산은 2진법에서 대응하는 각 비트 쌍을 더하되 올림을 버리는 것과 같다. 예를 들어
$$ 0\oplus 0=1\oplus 1=0, $$
$$ 1\oplus 0=0\oplus 1=1, $$
$$ 5\oplus 7=101_2\oplus 111_2=010_2=2. $$
베시에게는 소 화학물질이 담긴 상자 \(N\)개(\(1\le N\le 2\cdot 10^4\))가 있으며, \(i\)번째 상자에는 라벨이 \(l_i\)부터 \(r_i\)까지인 소 화학물질이 들어 있다\((0\le l_i \le r_i \le 10^9)\). 어떤 두 상자도 공통된 소 화학물질을 갖지 않는다. 베시는 서로 다른 세 가지 소 화학물질로 만들 수 있는 서로 다른 혼합물의 개수를 알고 싶어 한다. 한쪽에는 들어 있지만 다른 쪽에는 들어 있지 않은 소 화학물질이 하나라도 있으면 두 혼합물은 서로 다른 것으로 간주한다. 답이 매우 클 수 있으므로 \(10^9 + 7\)로 나눈 나머지를 출력한다.
문제 제공: Benjamin Qi
배점
- 테스트 케이스 3-4는 \(\max(K,r_N)\le 10^4\)를 만족한다.
- 테스트 케이스 5-6은 어떤 정수 \(k\ge 1\)에 대해 \(K=2^k-1\)을 만족한다.
- 테스트 케이스 7-11은 \(\max(K,r_N)\le 10^6\)을 만족한다.
- 테스트 케이스 12-16은 \(N\le 20\)을 만족한다.
- 테스트 케이스 17-21에는 추가 제약이 없다.
문제 제공: Benjamin Qi
첫째 줄에 두 정수 \(N\)과 \(K\)가 주어진다.
다음 \(N\)개의 줄 각각에는 공백으로 구분된 두 정수 \(l_i\)와 \(r_i\)가 주어진다. 소 화학물질 상자는 내용물의 오름차순으로 주어짐이 보장된다. 즉, 각 \(1\le i
베시가 만들 수 있는 서로 다른 세 가지 소 화학물질의 혼합물의 개수를 \(10^9 + 7\)로 나눈 나머지를 출력한다.
1 13
0 1994280We can split the chemicals into 13 groups that cannot cross-mix: \((0\ldots 15)\),
\((16\ldots 31)\), \(\ldots\) \((192\ldots 199)\). Each of the first twelve groups
contributes \(352\) unique mixtures and the last contributes \(56\) (since all
\(\binom{8}{3}\) combinations of three different cow-michals from
\((192\ldots 199)\) are okay), for a total of
\(352\cdot 12+56=4280\).
6 147
1 35
48 103
125 127
154 190
195 235
240 250267188riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > December > Platinum