AT_agc031_c [AGC031C] Differ by 1 Bit

题目描述

给定整数 $N,\ A,\ B$。请判断是否存在一个 $(0, 1, \ldots, 2^N-1)$ 的排列 $(P_0, P_1, \ldots, P_{2^N-1})$，满足以下所有条件。如果存在，请构造出一个解。

• $P_0 = A$。
• $P_{2^N-1} = B$。
• 对于所有 $0 \leq i < 2^N-1$，$P_i$ 和 $P_{i+1}$ 的二进制表示恰好只有一位不同。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A$ $B$

输出格式

如果不存在满足条件的排列，则输出 NO。

如果存在，首先输出一行 YES。然后第二行输出 $(P_0, P_1, \ldots, P_{2^N-1})$，用空格分隔。如果有多个解，输出任意一个均可。

样例 1

输入

2 1 3

输出

YES
1 0 2 3

样例 2

输入

3 2 1

输出

NO

说明/提示

限制条件

• $1 \leq N \leq 17$
• $0 \leq A \leq 2^N-1$
• $0 \leq B \leq 2^N-1$
• $A \neq B$
• 输入的所有数均为整数。

样例解释 1

将 $P=(1,0,2,3)$ 用二进制表示为 $(01, 00, 10, 11)$，可以发现任意相邻的两个元素恰好只有一位不同。

由 ChatGPT 4.1 翻译