Cowmistry

题目描述:

Bessie 的化学作业已经拖了很久，现在需要你的帮助！她需要用三种不同的化学品制造一种混合物。所有聪明的奶牛都知道，某些化学品之间不能进行混合，否则会产生爆炸。具体地说，两种标号为 a 和 b 的化学品当 a⊕b≤K （1≤K≤10⁹） 时可以出现在同一种混合物中。

注：这里，a⊕b 表示非负整数 a 与 b 的「异或」。这一运算等价于在二进制下将每一对应位相加并且舍弃进位。例如，

Bessie 有 N 盒化学品，第 i 个盒子内有标号从 li 到 ri 的化学品（0≤li≤ri≤10⁹）。没有两个盒子中含有同一种化学品。她想要知道她可以得到多少种由三种不同的化学品混合而成的混合物。如果至少一种化学品出现在一种混合物中而没有出现在另一种中，则认为这两种混合物是不同的。由于答案可能非常大，输出对10⁹+7 取模的结果。

输入格式:

输入的第一行包含两个整数 N 和 K。

以下 N 行，每行包含两个空格分隔的整数 li 和 ri。保证所有化学品盒子按其中内容的升序给出；也就是说，对所有 1≤i<N 有 r_i<l_i+1。

输出格式:

输出 Bessie 可以由三种不同化学品制造的混合物的数量，对 10⁹+7 取模。

样例输入:

样例1
1 13
0 199

样例2
6 147
1 35
48 103
125 127
154 190
195 235
240 250

样例输出:

样例1
4280

样例2
267188

提示:

我们可以将所有化学品分为不能交叉混合的 13 组：(0…15)， (16…31)，……(192…199)。前 12 组每组贡献了 352 种混合物，最后一组贡献了 56 种（因为所有 C(8,3) 种 (192…199) 中三种不同化学品的组合均可行），总共为 352⋅12+56=4280。

测试点性质：

• 测试点 3-4 满足 max(K,rN)≤10⁴。
• 测试点 5-6 对某个 k≥1 满足 K=2^k−1。
• 测试点 7-11 满足 max(K,rN)≤10⁶。
• 测试点 12-16 满足 N≤20。
• 测试点 17-21 没有额外限制。

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2020 DEC Platinum