题目描述
给定非负整数 $A, B$,定义有序非负整数对 $(x, y)$ 为好的当且仅当:
- $0 \le x \le y$;
- $x + y = A$;
- $x \operatorname{AND} y = B$。
其中 $\operatorname{AND}$ 代表按位与运算。在 C++ 语言中由 &
运算符表示。
你需要求出所有好的有序非负整数对 $(x, y)$ 的 $y - x$ 的和。
由于该值可能很大,你只需要输出其对 $M$ 取模后的结果。
形式化的,你需要求出
$$\left(\sum\limits_{x \ge 0}\sum\limits_{y \ge 0}\left(y - x\right)\left[\operatorname{good}(x, y)\right]\right)\bmod M$$
其中 $\operatorname{good}(x, y)$ 为真与有序非负整数对 $(x, y)$ 为好的等价。
输入格式
本题单个测试点内含有多组询问。
第一行两个整数 $T, M$,分别代表询问组数和模数。
接下来 $T$ 行,每行两个非负整数 $A, B$,代表一组询问。
输出格式
对于每组测试数据,输出一行一个整数,代表答案。
样例 #1
样例输入 #1
3 23
8 1
10 4
6 0
样例输出 #1
8
2
8
样例 #2
样例输入 #2
6 883
196483 132
330788 4353
137168 35030
615316 264202
387442 0
407154 0
样例输出 #2
579
432
0
27
807
845
样例 #3
样例输入 #3
3 30996377
948664793464517468 401148893358688606
945266152577109588 398323527798785832
185133025738933982 77893802910442339
样例输出 #3
29793121
28589865
30695563
样例 #4
样例输入 #4
5 992362009
248232552654965455 563160474979616
553521216364206023 14357560845404368
668113789984338832 146840018434951169
620025528908068087 506797735136774536
522926854352266209 860580850297773973
样例输出 #4
150959267
319548082
888288513
0
0
提示
【样例 #1 解释】
对于第一组询问,好的数对有 $\left(1, 7\right)$ 和 $\left(3, 5\right)$,因此答案为 $\left(7 - 1\right) + \left(5 - 3\right) = 8$。
对于第二组询问,好的数对只有 $\left(4, 6\right)$,因此答案为 $6 - 4 = 2$。
对于第三组询问,好的数对有 $\left(0, 6\right)$ 和 $\left(2, 4\right)$,因此答案为 $\left(6 - 0\right) + \left(4 - 2\right) = 8$。
【样例 #2 解释】
其所有询问均满足子任务 1 的限制,且后两组询问同时满足子任务 3 的限制。
特别的,在第三组询问的限制下,不存在好的有序非负整数对,因此答案为 $0$。
【样例 #3 解释】
其所有询问均满足子任务 2 的限制。
【样例 #4 解释】
其所有询问均满足子任务 4 的限制。
特别的,在第四、五组询问的限制下,不存在好的有序非负整数对,因此答案为 $0$。
【数据范围】
本题采用捆绑测试。
对于 $100\%$ 的数据:
- $1 \le T \le 3 \times 10^5$;
- $0 \le A, B < 2^{60}$;
- $5 \le M \le 1.1 \times 10^9$;
- $M$ 为质数。
具体部分分分配如下:
Subtask 编号 | 数据范围 | 分值 |
---|---|---|
1 | $T \le 200, 0 \le A, B \le 8 \times 10^5$ | $15$ |
2 | 对于每组询问,好的数对个数不超过 $1000$ 个 | $25$ |
3 | $B = 0$ | $25$ |
4 | 无特殊限制 | $35$ |