CF1815D.XOR Counting
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Given two positive integers n and m . Find the sum of all possible values of a1⨁a2⨁…⨁am , where a1,a2,…,am are non-negative integers such that a1+a2+…+am=n .
Note that all possible values a1⨁a2⨁…⨁am should be counted in the sum exactly once.
As the answer may be too large, output your answer modulo 998244353 .
Here, ⨁ denotes the bitwise XOR operation.
输入格式
Each test consists of multiple test cases. The first line contains a single integer t ( 1≤t≤104 ) — 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≤n≤1018,1≤m≤105 ) — the sum and the number of integers in the set, respectively.
输出格式
For each test case, output the sum of all possible values of a1⨁a2⨁…⨁am among all non-negative integers a1,a2,…,am with a1+a2+…+am=n . As the answer may be too large, output your answer modulo 998244353 .
输入输出样例
输入#1
7 69 1 5 2 0 10 420 69 12 26 73 34 1000000000000000000 10
输出#1
69 6 0 44310 42 1369 216734648
说明/提示
For the first test case, we must have a1=69 , so it's the only possible value of a1 , therefore our answer is 69 .
For the second test case, (a1,a2) can be (0,5),(1,4),(2,3),(3,2),(4,1) or (5,0) , in which a1⨁a2 are 5,5,1,1,5,5 respectively. So a1⨁a2 can be 1 or 5 , therefore our answer is 1+5=6 .
For the third test case, a1,a2,…,a10 must be all 0 , so a1⨁a2⨁…⨁a10=0 . Therefore our answer is 0 .