A6405. 「USACO 2020.12 Platinum」Cowmistry
编程题
NOI/NOI+/CTSC
知识点
题目描述
Bessie 的化学作业已经拖了很久，现在需要你的帮助！她需要用三种不同的化学品制造一种混合物。所有聪明的奶牛都知道，某些化学品之间不能进行混合，否则会产生爆炸。具体地说，两种标号为 $a$ 和 $b$ 的化学品当 $a⊕b≤K$（$1≤K≤10^9$） 时可以出现在同一种混合物中。
注：这里，$a⊕b$ 表示非负整数 $a$ 与 $b$ 的「异或」。这一运算等价于在二进制下将每一对应位相加并且舍弃进位。例如，
$$0⊕0=1⊕1=0$$
，
$$1⊕0=0⊕1=1$$
，
$$5⊕7=101_2⊕111_2=010_2=2$$
。
Bessie 有 $N(1\le N\le 2\cdot 10^4)$ 盒化学品，第 $i$ 个盒子内有标号从 $l_i$ 到 $r_i$ 的化学品（$0≤l_i≤r_i≤10^9$）。没有两个盒子中含有同一种化学品。她想要知道她可以得到多少种由三种不同的化学品混合而成的混合物。如果至少一种化学品出现在一种混合物中而没有出现在另一种中，则认为这两种混合物是不同的。由于答案可能非常大，输出对 $10^9+7$ 取模的结果。
注：这里，$a⊕b$ 表示非负整数 $a$ 与 $b$ 的「异或」。这一运算等价于在二进制下将每一对应位相加并且舍弃进位。例如，
$$0⊕0=1⊕1=0$$
，
$$1⊕0=0⊕1=1$$
，
$$5⊕7=101_2⊕111_2=010_2=2$$
。
Bessie 有 $N(1\le N\le 2\cdot 10^4)$ 盒化学品，第 $i$ 个盒子内有标号从 $l_i$ 到 $r_i$ 的化学品（$0≤l_i≤r_i≤10^9$）。没有两个盒子中含有同一种化学品。她想要知道她可以得到多少种由三种不同的化学品混合而成的混合物。如果至少一种化学品出现在一种混合物中而没有出现在另一种中，则认为这两种混合物是不同的。由于答案可能非常大，输出对 $10^9+7$ 取模的结果。
输入格式
输入的第一行包含两个整数 $N$ 和 $K$。
以下 $N$ 行，每行包含两个空格分隔的整数 $l_i$ 和 $r_i$。保证所有化学品盒子按其中内容的升序给出；也就是说，对所有 $1≤i<N$ 有 $r_i<l_i+1$。
以下 $N$ 行，每行包含两个空格分隔的整数 $l_i$ 和 $r_i$。保证所有化学品盒子按其中内容的升序给出；也就是说，对所有 $1≤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
说明/提示
测试点 $3\sim4$ 满足 $\max(K,r_N)≤10^4$。
测试点 $5\sim6$ 对某个 $k≥1$ 满足 $K=2^k−1$。
测试点 $7\sim11$ 满足 $\max(K,r_N)≤10^6$。
测试点 $12\sim16$ 满足 $N≤20$。
测试点 $17\sim21$ 没有额外限制。
测试点 $5\sim6$ 对某个 $k≥1$ 满足 $K=2^k−1$。
测试点 $7\sim11$ 满足 $\max(K,r_N)≤10^6$。
测试点 $12\sim16$ 满足 $N≤20$。
测试点 $17\sim21$ 没有额外限制。