AT_arc138_d [ARC138D] Differ by K bits
题目描述
给定整数 $N,K$。请判断是否存在一个 $ (0,1,\cdots,2^N-1) $ 的排列 $P=(P_0,P_1,\cdots,P_{2^N-1})$,使其满足以下条件,并在存在时构造出一个这样的排列。注意,$P$ 的下标从 $0$ 开始。
- 对于所有 $i$($0 \leq i \leq 2^N-1$),$P_i$ 和 $P_{(i+1)\bmod 2^N}$ 在二进制表示下恰好有 $K$ 位不同。比较时需将二者都补齐前导 $0$ 使其长度为 $N$ 位。
输入格式
输入从标准输入中给出,格式如下:
> $N$ $K$
输出格式
如果不存在满足条件的 $P$,输出 `No`。如果存在,输出如下格式的答案:
> Yes $P_0$ $P_1$ $\cdots$ $P_{2^N-1}$
如果有多个满足条件的解,输出任意一个均可。
说明/提示
### 限制
- $1 \leq K \leq N \leq 18$
- 所有输入值均为整数
### 样例解释 1
将 $P$ 用二进制表示为 $P=(000,001,011,010,110,111,101,100)$。例如 $P_1=001,P_2=011$,它们恰好有 $1$ 位不同,因此对于 $i=1$ 条件成立。对所有 $i$ 也都满足条件。
由 ChatGPT 4.1 翻译