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 翻译