Sequence Construction

题目描述

最近，农夫约翰农场里的奶牛们迷上了观看节目 Apothecowry Dairies。节目围绕着聪明的牛侦探 CowCow 解决各种各样的问题展开。Bessie 从节目中发现了一个新问题，但答案要等到一周后的下一集才会揭晓！请你替她解决这个问题。\n\n给定整数 $M$ 和 $K$ $(1 \leq M \leq 10 ^ 9, 1 \leq K \leq 31)$。\n请你选择一个正整数 $N$，并构造一个由 $N$ 个非负整数组成的序列 $a$，使得满足以下条件：\n$1 \le N \le 100$\n$a_1 + a_2 + \dots + a_N = M$\n$\text{popcount}(a_1) \oplus \text{ popcount}(a_2) \oplus \dots \oplus \text{ popcount}(a_N) = K$\n\n如果不存在这样的序列，输出 $-1$。\n\n$\dagger \text{ popcount}(x)$ 表示整数 $x$ 的二进制表示中等于 $1$ 的比特数。例如，$11$ 的 popcount 是 $3$，$16$ 的 popcount 是 $1$。\n\n$\dagger \oplus$ 表示按位异或运算符。\n\n输入包含 $T$ 个 $(1 \le T \le 5 \cdot 10^3)$ 相互独立的测试用例。

输入格式

第一行包含 $T$。\n每个测试用例仅一行，包含 $M$ 和 $K$。\n保证所有测试用例互不相同。

输出格式

按如下格式输出 $T$ 个测试用例的答案：\n如果不存在答案，则该测试用例只输出一行 $-1$。\n否则，该测试用例第一行输出一个整数 $N$，表示序列长度 -- ($1 \le N \le 100$)。\n第二行输出 $N$ 个用空格分隔的整数，满足题目条件 -- ($0 \le a_i \le M$)。

3\n2 1\n33 5\n10 5

2\n2 0\n3\n3 23 7 \n-1

提示

在第一个测试用例中，数组 $a = [2, 0]$ 的元素和为 $2$。popcount 的异或和为 $1 \oplus 0 = 1$。因此满足所有条件。\n\n在第二个测试用例中，数组 $a = [3, 23, 7]$ 的元素和为 $33$。popcount 的异或和为 $2 \oplus 4 \oplus 3 = 5$。因此满足所有条件。\n其他合法的数组还有 $a = [4, 2, 15, 5, 7]$ 和 $a = [1, 4, 0, 27, 1]$。\n可以证明第三个测试用例不存在合法数组。\n\nSCORING:\nInput 2: $M \leq 8, K \leq 8$\nInputs 3-5: $M > 2^K$\nInputs 6-18: 无额外限制。\n\n题目来源：Aakash Gokhale

标签: USACO|2025|Silver

来源

USACO|2025|Silver