CFCF2180C.XOR-factorization

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Ostad 认为通常的因数分解方式过于数学化，因此他发明了一种被称为“异或因数分解”的新概念，更加偏向计算机科学。对于给定的整数 $n$ ，一组整数序列 $a_1, a_2, \ldots, a_k$ ，其中 $0 \le a_i \le n$ 对于所有 $i$ ，被称为 $n$ 的异或因数分解，当且仅当

$a_1 \oplus a_2 \oplus \cdots \oplus a_k = n,$

其中 $\oplus$ 表示按位异或运算。

给定整数 $n$ 和 $k$ ，请找到一组 $n$ 的异或因数分解 $a_1, a_2, \ldots, a_k$ ，使得 $a_1 + a_2 + \cdots + a_k$ 的和最大。

可以证明，在题目给定的条件下，总能找到异或因数分解。

输入格式

每组测试包含多个测试用例。第一行包含测试用例个数 $t$ （ $1 \le t \le 10^4$ ）。接下来每行包含两个整数 $n$ 和 $k$ （ $1 \le n \le 10^9$ ， $1 \le k \le 10^5$ ）。

保证所有测试用例中 $k$ 的总和不超过 $10^5$ 。

输出格式

对于每个测试用例，输出 $k$ 个整数 $a_1, a_2, \ldots, a_k$ ，满足 $0 \le a_i \le n$ 。

可以证明，答案一定存在。如果有多组合法答案，你可以按任意顺序输出其中一组。

输入输出样例

输入#1
```
4
5 4
4 3
8 2
1 1
```
输出#1
```
1 4 5 5
4 4 4
0 8
1
```

说明/提示

在第一个测试用例中，我们可以将 $5$ 分解为 $1 \oplus 4 \oplus 5 \oplus 5$ ，此时和为 $15$ ，可以证明不存在使异或和为 $5$ 且总和更大的分解方式。

在第二个测试用例中，我们可以将 $4$ 分解为 $4 \oplus 4 \oplus 4$ ，总和为 $12$ ，这显然是可能的最大值。

首页