#PU1070. USACO 2020 December Contest, Platinum — Problem 3. Cowmistry

    ID: 1188 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec20来源:usaco.orgscoring:equal_test_cases二分枚举

USACO 2020 December Contest, Platinum — Problem 3. Cowmistry

USACO 2020 December Contest, Platinum — Problem 3. Cowmistry

题目描述

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 aa and bb can only be present in the same mixture if a⊕b≤Ka \oplus b \le K (1≤K≤1091 \le K \le 10^9).

输入格式

The first line contains two integers NN and KK. Each of the next NN lines contains two space-separated integers lil_i and rir_i. It is guaranteed that the boxes of cow-michals are provided in increasing order of their contents; namely, ri<li+1r_i<l_{i+1} for each 1≤i<N1\le i<N.

输出格式

The number of mixtures of three different cow-michals Bessie can create, modulo 109+710^9 + 7.

数据范围

Test cases 3-4 satisfy max⁡(K,rN)≤104\max(K,r_N)\le 10^4. Test cases 5-6 satisfy K=2k−1K=2^k-1 for some integer k≥1k\ge 1. Test cases 7-11 satisfy max⁡(K,rN)≤106\max(K,r_N)\le 10^6. Test cases 12-16 satisfy N≤20N\le 20. Test cases 17-21 satisfy no additional constraints. Problem credits: Benjamin Qi

样例

样例 1

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$.

样例 2

6 147
1 35
48 103
125 127
154 190
195 235
240 250
267188

提示

integers aa and bb. This operation is equivalent to adding each corresponding pair of bits in base 2 and discarding the carry. For example,

0⊕0=1⊕1=0,0\oplus 0=1\oplus 1=0, 1⊕0=0⊕1=1,1\oplus 0=0\oplus 1=1, 5⊕7=1012⊕1112=0102=2.5\oplus 7=101_2\oplus 111_2=010_2=2.

Bessie has NN (1≤N≤2⋅1041\le N\le 2\cdot 10^4) boxes of cow-michals and the ii-th box contains cow-michals labeled lil_i through rir_i inclusive (0≤li≤ri≤109)(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 109+710^9 + 7.