XOR Counting
Contest: Codeforces Round 865 (Div. 1)
Difficulty rating: 2600
Tags: bitmasks, combinatorics, dp, math

Given two positive integers $$$n$$$ and $$$m$$$. Find the sum of all possible values of $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$, where $$$a_1,a_2,\ldots,a_m$$$ are non-negative integers such that $$$a_1+a_2+\ldots+a_m=n$$$.

Note that all possible values $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$ should be counted in the sum exactly once.

As the answer may be too large, output your answer modulo $$$998244353$$$.

Here, $$$\bigoplus$$$ denotes the bitwise XOR operation.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.

The first and only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$0\le n\le 10^{18}, 1\le m\le 10^5$$$) — the sum and the number of integers in the set, respectively.

Output format:
For each test case, output the sum of all possible values of $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$ among all non-negative integers $$$a_1,a_2,\ldots,a_m$$$ with $$$a_1+a_2+\ldots+a_m=n$$$. As the answer may be too large, output your answer modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case, we must have $$$a_1=69$$$, so it's the only possible value of $$$a_1$$$, therefore our answer is $$$69$$$.

For the second test case, $$$(a_1,a_2)$$$ can be $$$(0,5), (1,4), (2,3), (3,2), (4,1)$$$ or $$$(5,0)$$$, in which $$$a_1\bigoplus a_2$$$ are $$$5,5,1,1,5,5$$$ respectively. So $$$a_1\bigoplus a_2$$$ can be $$$1$$$ or $$$5$$$, therefore our answer is $$$1+5=6$$$.

For the third test case, $$$a_1,a_2,\ldots,a_{10}$$$ must be all $$$0$$$, so $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_{10}=0$$$. Therefore our answer is $$$0$$$.

Example input:
7
69 1
5 2
0 10
420 69
12 26
73 34
1000000000000000000 10

Example output:
69
6
0
44310
42
1369
216734648

Editorial:
If $$$m=1$$$, it is clear that we only can have $$$a_1=n$$$ so the answer is $$$n$$$.
If $$$m\ge3$$$, $$$\left[x,\frac{n-x}2,\frac{n-x}2,0,0,...\right]$$$ gives a xor of $$$x$$$, so all $$$x$$$ with the same parity as $$$n$$$ and at most $$$n$$$ can be achieved. Notice xor and sum are identical in terms of parity, and $$$a\oplus b\le a+b$$$. So these restrict that only values of $$$x$$$ that has same parity with $$$n$$$ and is at most $$$n$$$ is possible as a result of the xor. Therefore, we can use $$$O(1)$$$ to calculate the sum of all non-negative integers at most $$$n$$$ and have same parity as $$$n$$$.
It remains to handle the case when $$$m=2$$$. We create the functions $$$f(n)$$$ and $$$g(n)$$$, where $$$f(n)$$$ is the sum of all possible values of the xor and $$$g(n)$$$ counts the number of all possible values of the xor. We then consider the following:
If $$$n$$$ is odd, then one of $$$a_1,a_2$$$ is even and the other is odd. WLOG assume $$$a_1$$$ is even and $$$a_2$$$ is odd. Then we let $$$a_1'=\frac{a_1}2$$$ and $$$a_2'=\frac{a_2-1}2$$$. We can see that $$$a_1'+a_2'=\frac{n-1}2$$$ and $$$a_1\oplus a_2=2(a_1'\oplus a_2')+1$$$. Hence we know that $$$g(n)=g\left(\frac{n-1}2\right)$$$, and $$$f(n)=2f\left(\frac{n-1}2\right)+g\left(\frac{n-1}2\right)$$$.
If $$$n$$$ is even, there are two cases. If $$$a_1$$$ and $$$a_2$$$ are both even, we let $$$a_1'=\frac{a_1}2$$$ and $$$a_2'=\frac{a_2}2$$$. We can see that $$$a_1'+a_2'=\frac{n}2$$$ and $$$a_1\oplus a_2=2(a_1'\oplus a_2')$$$. If $$$a_1$$$ and $$$a_2$$$ are both odd, we let $$$a_1'=\frac{a_1-1}2$$$ and $$$a_2'=\frac{a_2-1}2$$$. We can see that $$$a_1'+a_2'=\frac{n}2-1$$$ and $$$a_1\oplus a_2=2(a_1'\oplus a_2')$$$. Hence we know that $$$f(n)=2f\left(\frac{n}2\right)+2f\left(\frac{n}2-1\right)$$$, and $$$g(n)=g\left(\frac{n}2\right)+g\left(\frac{n}2-1\right)$$$.
So we can simply DP. It can be seen that the time complexity is $$$O(\log n)$$$ per test case, so we are done.