CF925C Big Secret

题目描述

Vitya 发现生命、宇宙以及一切问题的终极答案并不是整数 $54\ 42$,而是一个递增的整数序列 $a_1, \ldots, a_n$。为了不让秘密过早泄露,Vitya 对答案进行了加密,得到了序列 $b_1, \ldots, b_n$,加密规则如下: - $b_1 = a_1$; - 对于所有 $i$ 从 $2$ 到 $n$,有 $b_i = a_i \oplus a_{i-1}$,其中 $x \oplus y$ 表示 $x$ 和 $y$ 的按位异或。 显然,可以通过如下规则还原原始序列:$a_i = b_1 \oplus \ldots \oplus b_i$。 然而,过了一段时间,Vitya 发现密文中的整数 $b_i$ 被打乱了顺序。这样一来,如果仍然按照上述规则解密,可能得到的序列并不是递增的。为了挽回自己在科学界的声誉,Vasya 决定找到一种 $b_i$ 的排列方式,使得 $a_i = b'_1 \oplus \ldots \oplus b'_i$ 形成一个严格递增的序列。请你帮助他找到这样一种排列,或者判断是否不存在这样的排列。

输入格式

第一行包含一个整数 $n$($1 \leq n \leq 10^5$)。 第二行包含 $n$ 个整数 $b_1, \ldots, b_n$($1 \leq b_i < 2^{60}$)。

输出格式

如果不存在合法的排列,输出一行 "No"。 否则,第一行输出 "Yes",第二行输出 $b'_1, \ldots, b'_n$,表示一种合法的排列。无序多重集 $\{b_1, \ldots, b_n\}$ 和 $\{b'_1, \ldots, b'_n\}$ 应当相同,即对于每个整数 $x$,在两个多重集中出现的次数应当相等。此外,序列 $a_i = b'_1 \oplus \ldots \oplus b'_i$ 必须严格递增。 如果有多种答案,输出任意一种即可。

说明/提示

在第一个样例中,没有合法的排列。 在第二个样例中,给定的答案会得到序列 $a_1 = 4$,$a_2 = 8$,$a_3 = 15$,$a_4 = 16$,$a_5 = 23$,$a_6 = 42$。 由 ChatGPT 4.1 翻译