Cowmistry

题目描述

Bessie 一直在拖延她的奶牛化学（cow-mistry）作业，现在需要你的帮助！她需要配制一种由三种不同 cow-michal 组成的混合物。众所周知，有些 cow-michal 不能相互混合，否则会发生爆炸。具体来说，标签为 $a$ 和 $b$ 的两种 cow-michal 只有在满足 $a \oplus b \le K$（$1 \le K \le 10^9$）时，才能同时出现在同一份混合物中。 注意：这里的 $a\oplus b$ 表示非负整数 $a$ 与 $b$ 的“按位异或”。该运算等价于在二进制下逐位相加并丢弃进位。例如，

Bessie 有 $N$（$1\le N\le 2\cdot 10^4$）个装有 cow-michal 的盒子，第 $i$ 个盒子包含标签从 $l_i$ 到 $r_i$（含端点）的 cow-michal（$(0\le l_i \le r_i \le 10^9)$）。任意两个盒子中的 cow-michal 没有重叠。她想知道她能配制出多少种由三种不同 cow-michal 组成的不同混合物。若两份混合物中至少有一种 cow-michal 在其中一份出现而另一份未出现，则认为这两份混合物不同。由于答案可能非常大，请输出对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含两个整数 $N$ 和 $K$。 接下来 $N$ 行，每行包含两个以空格分隔的整数 $l_i$ 和 $r_i$。保证这些盒子按其内容递增顺序给出；即对每个 $1\le i<N$，都有 $r_i<l_{i+1}$。

输出格式

输出 Bessie 可以配制的由三种不同 cow-michal 组成的混合物数量，并对 $10^9 + 7$ 取模。

1 13
0 199

4280

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

267188

提示

我们可以将这些化学品分成 13 个无法相互混合的组：$(0\ldots 15)$、$(16\ldots 31)$、$\ldots$、$(192\ldots 199)$。前 12 组每组贡献 $352$ 种不同的混合物，最后一组贡献 $56$（因为从 $(192\ldots 199)$ 中任选三种不同 cow-michal 的所有 $\binom{8}{3}$ 种组合都可行），总计为 $352\cdot 12+56=4280$。 SCORING 测试点 3-4 满足 $\max(K,r_N)\le 10^4$。 测试点 5-6 满足 $K=2^k-1$，其中 $k\ge 1$ 为某个整数。 测试点 7-11 满足 $\max(K,r_N)\le 10^6$。 测试点 12-16 满足 $N\le 20$。 测试点 17-21 无额外限制。 题目鸣谢：Benjamin Qi

标签: USACO|2020|Platinum

来源

USACO|2020|Platinum