Вам даны два положительных целых числа $$$n$$$ и $$$m$$$. Найдите сумму всех возможных значений $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$, где $$$a_1,a_2,\ldots,a_m$$$ являются неотрицательными целыми числами такими, что $$$a_1+a_2+\ldots+a_m=n$$$.
Обратите внимание, что все возможные значения $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$ должны быть посчитаны в сумме ровно один раз.
Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.
Здесь $$$\bigoplus$$$ обозначает операцию побитового исключающего ИЛИ.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая и единсвственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$0\le n\le 10^{18}, 1\le m\le 10^5$$$) — сумма и количество чисел в наборе, соответственно.
Для каждого набора входных данных выведите сумму всех возможных значений $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$ по всем наборам неотрицательных целых чисел $$$a_1,a_2,\ldots,a_m$$$ с $$$a_1+a_2+\ldots+a_m=n$$$. Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.
769 15 20 10420 6912 2673 341000000000000000000 10
69 6 0 44310 42 1369 216734648
В первом наборе входных данных у нас должно быть $$$a_1=69$$$, поэтому это единственное возможное значение $$$a_1$$$, следовательно, наш ответ — $$$69$$$.
Во втором наборе входных данных $$$(a_1,a_2)$$$ может быть равно $$$(0,5), (1,4), (2,3), (3,2), (4,1)$$$ или $$$(5,0)$$$, в которых $$$a_1\bigoplus a_2$$$ равно $$$5,5,1,1,5,5$$$ соответственно. Поэтому $$$a_1\bigoplus a_2$$$ может быть равно $$$1$$$ или $$$5$$$, поэтому ответ равен $$$1+5=6$$$.
В третьем наборе входных данных $$$a_1,a_2,\ldots,a_{10}$$$ должны быть все равны $$$0$$$, поэтому $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_{10}=0$$$. Поэтому ответ равен $$$0$$$.
| Codeforces Round 865 (Div. 1) |
|---|
| Закончено |
