P12147 【MX-X11-T1】That Alone is Enough

原题链接：。 --- $$\text{もうさ強がらなくてもいいんだよ}$$ $$\text{過去の夜の涙ひとつ}$$ $$\text{それを柔く持って歩いて征く}$$ $$\text{それだけで今はいいんだよ}$$

Define $f(x) = x \oplus (x + 2^k)$, where $\oplus$ denotes the bitwise XOR operation. Given two integers $n$ and $k$, compute the value of $f(0) + f(1) + f(2) + \cdots + f(n)$. For knowledge about XOR operations, you may refer to the [Wikipedia Page](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

**Multiple test cases.** The first line contains a positive integer $T$ indicating the number of test cases. Each of the next $T$ lines contains two integers $n$ and $k$.

Output $T$ lines, each containing the answer for the corresponding query.

## Explanation #1 **Sample 1 Explanation:** For the first test case: - $f(0) = 0 \oplus (0 + 2^0) = 1$ - $f(1) = 1 \oplus (1 + 2^0) = 3$ - $f(2) = 2 \oplus (2 + 2^0) = 1$ - $f(3) = 3 \oplus (3 + 2^0) = 7$ Thus, the answer is $1 + 3 + 1 + 7 = 12$. ## Constraints - **20% of data**: $n, T \leq 5000$ - **Additional 20% of data**: $n \leq 10^5$ - **Additional 30% of data**: $k = 0$ - **100% of data**: $1 \leq T \leq 10^5$, $0 \leq n < 2^{29}$, $0 \leq k \leq 29$ Translated by DeepSeek R1