P12025 [USACO25OPEN] Sequence Construction S

题目描述

最近，农夫约翰农场里的奶牛们迷上了观看《炼乳神探》这档节目。节目讲述了一头聪明的奶牛侦探CowCow解决各类案件的故事。贝茜从节目中发现了新的谜题，但答案要等到下周的下一集才会揭晓！请帮她解决这个问题。

给定整数 $M$ 和 $K$ $(1 \leq M \leq 10^9, 1 \leq K \leq 31)$。请选择一个正整数 $N$ 并构造一个包含 $N$ 个非负整数的序列 $a$，满足以下条件：

• $1 \le N \le 100$。
• $a_1 + a_2 + \dots + a_N = M$。
• $\text{popcount}(a_1) \oplus \text{ popcount}(a_2) \oplus \dots \oplus \text{ popcount}(a_N) = K$。

如果不存在这样的序列，输出 $-1$。

$\dagger \text{ popcount}(x)$ 表示整数 $x$ 的二进制表示中 $1$ 的位数。例如，$11$ 的 popcount 是 $3$，$16$ 的 popcount 是 $1$。

$\dagger \oplus$ 表示按位异或运算符。

输入包含 $T$ ($1 \le T \le 5 \cdot 10^3$) 组独立测试用例。

输入格式

第一行包含 $T$。

每个测试用例的第一行也是唯一一行包含 $M$ 和 $K$。

保证所有测试用例都是唯一的。

输出格式

按以下方式输出 $T$ 个测试用例的解答：

如果无解，该测试用例对应的唯一一行输出应为 $-1$。

否则，该测试用例的第一行输出应为序列长度 $N$（$1 \le N \le 100$），第二行输出应包含 $N$ 个用空格分隔且满足条件的整数（$0 \le a_i \le M$）。

输入输出样例 #1

输入 #1

3
2 1
33 5
10 5

输出 #1

2
2 0
3
3 23 7 
-1

说明/提示

在第一个测试用例中，数组 $a = [2, 0]$ 的元素之和为 $2$。其 popcount 的异或和为 $1 \oplus 0 = 1$，因此所有条件均被满足。

在第二个测试用例中，数组 $a = [3, 23, 7]$ 的元素之和为 $33$。其 popcount 的异或和为 $2 \oplus 4 \oplus 3 = 5$，因此所有条件均被满足。

其他有效数组包括 $a = [4, 2, 15, 5, 7]$ 和 $a = [1, 4, 0, 27, 1]$。

可以证明第三个测试用例不存在有效数组。

• 测试点 $2$：$M \leq 8, K \leq 8$。
• 测试点 $3\sim 5$：$M > 2^K$。
• 测试点 $6\sim18$：无额外限制。