Bessie has been procrastinating on her cow-mistry homework and now needs your
help! She needs to create a mixture of three different cow-michals. As all good
cows know though, some cow-michals cannot be mixed with each other or else they
will cause an explosion. In particular, two cow-michals with labels \(a\) and \(b\)
can only be present in the same mixture if \(a \oplus b \le K\)
(\(1 \le K \le 10^9\)).

NOTE: Here, \(a\oplus b\) denotes the "bitwise exclusive or'' of non-negative
integers \(a\) and \(b\). This operation is equivalent to adding each corresponding
pair of bits in base 2 and discarding the carry. For example,
$$ 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. $$

Bessie has \(N\) (\(1\le N\le 2\cdot 10^4\)) boxes of cow-michals and the \(i\)-th box contains cow-michals
labeled \(l_i\) through \(r_i\) inclusive \((0\le l_i \le r_i \le 10^9)\). No two
boxes have any cow-michals in common. She wants to know how many unique mixtures
of three different cow-michals she can create. Two mixtures are considered
different if there is at least one cow-michal present in one but not the other.
Since the answer may be very large, report it modulo \(10^9 + 7\).

Problem credits: Benjamin Qi

SCORING

• Test cases 3-4 satisfy \(\max(K,r_N)\le 10^4\).
• Test cases 5-6 satisfy \(K=2^k-1\) for some integer \(k\ge 1\).
• Test cases 7-11 satisfy \(\max(K,r_N)\le 10^6\).
• Test cases 12-16 satisfy \(N\le 20\).
• Test cases 17-21 satisfy no additional constraints.

Problem credits: Benjamin Qi

The first line contains two integers \(N\) and \(K\).

Each of the next \(N\) lines contains two space-separated integers \(l_i\) and
\(r_i\). It is guaranteed that the boxes of cow-michals are provided in increasing
order of their contents; namely, \(r_i for each \(1\le i.

The number of mixtures of three different cow-michals Bessie can create, modulo
\(10^9 + 7\).

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > December > Platinum