← 返回题目列表

AtCoder · arc138_d

D. 相差 K 位

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给你整数 N 和 K。 判断是否存在排列 P=(P_0,P_1,\cdots,P_{2^N-1}) of (0,1,\cdots,2^N-1) 满足以下条件,并构造一个这样的序列(如果存在)。请注意 P is 0- 索引。

  • 对于每个 i (0 \leq i \leq 2^N-1), P_i 和 P_{i+1 \mod 2^N} 的不同之处在于 二进制表示的 K 位。 将两个整数补零后进行比较 N 位。

约束

  • 1 \leq K \leq N \leq 18
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K

输出

如果没有 P 满足条件,打印 No。 如果有这样一个 P,按以下格式打印:

Yes
P_0 P_1 \cdots P_{2^N-1}

如果有多个解满足条件,则打印任意一个。


示例输入 1

3 1

示例输出 1

Yes
0 1 3 2 6 7 5 4

在这里,我们有 二进制表示的 P=(000,001,011,010,110,111,101,100) 。

我们可以看到 例如, P_1=001 和 P_2=011的不同之处在于 1 位,满足条件 i=1。 每个都一样 i.


示例输入 2

2 2

示例输出 2

No