No.3444 Interval Xor MST
Problem Statement
You are given a positive integer $N$ and a non-negative integer $M$.
The vertices of a weighted complete graph $G$ with $N$ vertices are numbered from $0$ to $N - 1$, and for any $0 \leq a < b < N$, the weight of the edge connecting vertex $a$ and vertex $b$ is $(a + M) \oplus (b + M)$. Here, $\oplus$ denotes the bitwise exclusive OR.
Find the sum of the edge weights of a minimum spanning tree of $G$.
You are given $T$ test cases; solve each of them.
Constraints
- $1\leq T\leq 10^{5}$
- $1\leq N\leq 2\times 10^{9}$
- $0\leq M\leq 2\times 10^{9}$
- All input values are integers.
Input
The input is given from Standard Input in the following format.
$T$
$case_{1}$
$case_{2}$
$\vdots$
$case_{T}$
Each case is given in the following format.
$N$ $M$
Output
Output $T$ lines.
On the $i$-th line, output the answer for $case_{i}$.
Sample
Sample 1
Input
3 3 2 167 924 1234567890 1234567890
Output
7 2551 21772702017
For the $1$st test case, the following holds for the edge weights.
- The weight of the edge connecting vertex $0$ and vertex $1$ is $(0 + 2)\oplus(1 + 2)=1$.
- The weight of the edge connecting vertex $0$ and vertex $2$ is $(0 + 2)\oplus(2 + 2)=6$.
- The weight of the edge connecting vertex $1$ and vertex $2$ is $(1 + 2)\oplus(2 + 2)=7$.
Therefore, the minimum spanning tree consists of $2$ edges: the edge connecting vertex $0$ and vertex $1$, and the edge connecting vertex $0$ and vertex $2$.
On the $1$st line, output the sum of these edge weights, $1 + 6 = 7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2