310322: CF1815D. XOR Counting
Description
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.
InputEach 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.
OutputFor 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$.
ExampleInput7 69 1 5 2 0 10 420 69 12 26 73 34 1000000000000000000 10Output
69 6 0 44310 42 1369 216734648Note
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$.
Input
题意翻译
### 题目描述 记 $\bigoplus$ 表示按位异或运算。 给定整数 $n,m$。 记一个序列 $a$ 是好的，当且仅当它是一个长度为 $m$ 的非负整数序列，且其元素之和恰好为 $n$。 求在好的序列 $a$ 中，$\bigoplus_{i=1}^ma_i$ 的所有可能取值之和对 $998244353$ 取模后的值。 **对于一个 $\bm{\bigoplus_{i=1}^ma_i}$ 的可能取值，无论有多少个可以取得这个值的好的序列 $\bm{a}$，这个值都应只被计入所求之和一次。** 每个测试点包含 $t$ 组数据。 ### 输入格式 第一行输入一个整数 $t(1\leq t\leq10^4)$ 表示数据组数，接下来对于每组数据： 输入一行两个整数 $n,m(0\leq n\leq10^{18};1\leq m\leq10^5)$。 ### 输出格式 对于每组数据： 输出一行一个整数表示 $\bigoplus_{i=1}^ma_i$ 的所有可能取值之和对 $998244353$ 取模后的值。 ### 样例解释 对于样例一： - 所有好的序列 $a$ 为 $[69]$，其所有元素按位异或和为 $69$。 因此 $\bigoplus_{i=1}^ma_i$ 的所有可能取值为 $69$，故答案为 $69$。 对于样例二： - 所有好的序列 $a$ 为 $[5,0],[4,1],[3,2],[2,3],[4,1],[0,5]$，其所有元素按位异或和分别为 $5,5,1,1,5,5$。 因此 $\bigoplus_{i=1}^ma_i$ 的所有可能取值为 $1,5$，故答案为 $1+5$，即 $6$。 对于样例三： - 所有好的序列 $a$ 为 $[0,0,0,0,0,0,0,0,0,0]$，其所有元素按位异或和为 $0$。 因此 $\bigoplus_{i=1}^ma_i$ 的所有可能取值为 $0$，故答案为 $0$。Output
输入数据格式：每个测试包含多个测试用例。第一行包含一个整数 \( t \)（\( 1 \le t \le 10^4 \)）——测试用例的数量。接下来是每个测试用例的描述。每个测试用例的第一行包含两个整数 \( n \) 和 \( m \)（\( 0 \le n \le 10^{18}, 1 \le m \le 10^5 \)）——集合中的和以及整数的数量。
输出数据格式：对于每个测试用例，输出所有可能的 \( a_1 \oplus a_2 \oplus \ldots \oplus a_m \) 的和，对所有非负整数 \( a_1, a_2, \ldots, a_m \) 而言，其和为 \( n \)。输出答案对 \( 998244353 \) 取模的结果。题目大意：给定两个正整数 \( n \) 和 \( m \)，求所有可能的 \( a_1 \oplus a_2 \oplus \ldots \oplus a_m \) 的和，其中 \( a_1, a_2, \ldots, a_m \) 是非负整数，且 \( a_1 + a_2 + \ldots + a_m = n \)。所有的 \( a_1 \oplus a_2 \oplus \ldots \oplus a_m \) 的值都应该被计算一次。由于答案可能很大，输出答案对 \( 998244353 \) 取模的结果。这里的 \( \oplus \) 表示按位异或操作。 输入数据格式：每个测试包含多个测试用例。第一行包含一个整数 \( t \)（\( 1 \le t \le 10^4 \)）——测试用例的数量。接下来是每个测试用例的描述。每个测试用例的第一行包含两个整数 \( n \) 和 \( m \)（\( 0 \le n \le 10^{18}, 1 \le m \le 10^5 \)）——集合中的和以及整数的数量。 输出数据格式：对于每个测试用例，输出所有可能的 \( a_1 \oplus a_2 \oplus \ldots \oplus a_m \) 的和，对所有非负整数 \( a_1, a_2, \ldots, a_m \) 而言，其和为 \( n \)。输出答案对 \( 998244353 \) 取模的结果。