3530. [USACO20Dec Platinum]Cowmistry

【题目描述】

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

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

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

【输入格式】

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

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

【输出格式】

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

【样例输入1】

1 13
0 199

【样例输出1】

4280

【样例输入2】

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

【样例输出2】

267188

【样例说明】

【样例 1 解释】

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

【数据规模与约定】

对于$ 19\% $的测试数据(测试点$ 1\sim4 $)，满足 $\max(K,r_N)\le 10^4$。

另有$ 10\% $的测试数据(测试点$ 5\sim6 $)，对某个 $k\ge 1$ 满足 $K=2^k-1$。

另有$ 24\% $的测试数据(测试点$ 7\sim11 $)，满足 $\max(K,r_N)\le 10^6$。

另有$ 24\% $的测试数据(测试点$ 12\sim16 $)，满足 $N\le 20$。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 十二月月赛 Platinum 组