| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 6 | 6 | 6 | 100.000% |
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,
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$.
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<l_{i+1}$ for each 1ドル\le i<N$.
The number of mixtures of three different cow-michals Bessie can create, modulo 10ドル^9 + 7$.
1 13 0 199
4280
We 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 250
267188