CF1734F Zeros and Ones
题目描述
设 $S$ 为 [Thue-Morse 序列](https://en.wikipedia.org/wiki/Thue-Morse_sequence)。换句话说，$S$ 是一个以 $0$ 开头的无限长二进制字符串，可以按如下方式构造：
- 初始时，令 $S$ 为 "0"。
- 然后，无限次执行以下操作：将 $S$ 与其自身的按位取反副本拼接。例如，前四次迭代如下所示：
| 迭代次数 | 迭代前的 $S$ | 迭代前的 $S$ 的按位取反 | 拼接后的 $S$ |
|:--------:|:------------:|:-----------------------:|:------------:|
| 1 | 0 | 1 | 01 |
| 2 | 01 | 10 | 0110 |
| 3 | 0110 | 1001 | 01101001 |
| 4 | 01101001 | 10010110 | 0110100110010110 |
| ... | ... | ... | ... |
你将得到两个正整数 $n$ 和 $m$。请你计算字符串 $S_0 S_1 \ldots S_{m-1}$ 与 $S_n S_{n+1} \ldots S_{n+m-1}$ 在对应位置上有多少个不同的字符。
输入格式
每组测试数据包含多组测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来的每组测试用例包含一行，包含两个正整数 $n$ 和 $m$（$1 \leq n, m \leq 10^{18}$）。
输出格式
对于每组测试用例，输出一个非负整数，表示所求的两个字符串的汉明距离。
说明/提示
字符串 $S$ 等于 0110100110010110...。
在第一个测试用例中，$S_0$ 是 "0"，$S_1$ 是 "1"。这两个字符串的汉明距离为 $1$。
在第二个测试用例中，$S_0 S_1 \ldots S_9$ 是 "0110100110"，$S_5 S_6 \ldots S_{14}$ 是 "0011001011"。这两个字符串的汉明距离为 $6$。
由 ChatGPT 4.1 翻译