CF1934D1 XOR Break — Solo Version

题目描述

这是该问题的单人版本。请注意,本题的解法与游戏版本的解法可能相同,也可能不同。你可以分别独立地解决这两个版本并获得积分。 只有当你同时解决了这两个版本的问题时,才能进行 Hack。 给定一个整数变量 $x$,初始值为 $n$。一次 break 操作包括以下步骤: - 选择一个值 $y$,满足 $0 < y < x$ 且 $0 < (x \oplus y) < x$。 - 将 $x$ 更新为 $x = y$ 或 $x = x \oplus y$。 请判断是否可以在最多 $63$ 次 break 操作内将 $x$ 变为 $m$。如果可以,请给出实现 $x = m$ 所需的操作序列。你不需要最小化操作次数。 这里 $ \oplus $ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。

输入格式

第一行包含一个正整数 $t$($1 \le t \le 10^4$),表示测试用例的数量。 每个测试用例包含一行,包含两个整数 $n$ 和 $m$($1 \leq m < n \leq 10^{18}$),分别表示 $x$ 的初始值和目标值。

输出格式

对于每个测试用例,按以下格式输出答案。 如果无法在 $63$ 次操作内得到 $m$,输出 $-1$。 否则, 第一行输出一个整数 $k$($1 \leq k \leq 63$),表示所需操作次数。 第二行输出 $k+1$ 个整数,表示每次 break 操作后 $x$ 的变化序列。第 $1$ 个和第 $k+1$ 个整数应分别为 $n$ 和 $m$。

说明/提示

在第一个测试用例中,$n = 7$,第一次操作时 $x = 7$,如果选择 $y = 3$,则有 $(7 \oplus 3) < 7$,因此我们可以将 $x$ 更新为 $3$,这正好等于 $m$。 在第二个测试用例中,$n = 4$,第一次操作时 $x = 4$。 如果选择: - $y = 1$,则 $(4 \oplus 1) > 4$ - $y = 2$,则 $(4 \oplus 2) > 4$ - $y = 3$,则 $(4 \oplus 3) > 4$ 因此无法进行第一次操作,也就无法使 $x = 2$。 由 ChatGPT 4.1 翻译