P10118 『STA - R4』And

给定非负整数 $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)$ 为好的等价。

无

无

**【样例 #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$|