#P13674. [ARC138D] Differ by K bits

    ID: 12876 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-奇偶性分析线性基异或消元格雷码格雷码相邻状态增量更新排列构造位计数

[ARC138D] Differ by K bits

题目描述

给定整数 N,KN,K。请判断是否存在一个 (0,1,⋯ ,2N−1) (0,1,\cdots,2^N-1) 的排列 P=(P0,P1,⋯ ,P2N−1)P=(P_0,P_1,\cdots,P_{2^N-1}),使其满足以下条件,并在存在时构造出一个这样的排列。注意,PP 的下标从 00 开始。

  • 对于所有 ii(0≤i≤2N−10 \leq i \leq 2^N-1),PiP_i 和 P(i+1) mod 2NP_{(i+1)\bmod 2^N} 在二进制表示下恰好有 KK 位不同。比较时需将二者都补齐前导 00 使其长度为 NN 位。

输入格式

输入从标准输入中给出,格式如下:

NN KK

输出格式

如果不存在满足条件的 PP,输出 No。如果存在,输出如下格式的答案:

Yes P0P_0 P1P_1 ⋯\cdots P2N−1P_{2^N-1}

如果有多个满足条件的解,输出任意一个均可。

输入输出样例 #1

输入 #1

3 1

输出 #1

Yes
0 1 3 2 6 7 5 4

输入输出样例 #2

输入 #2

2 2

输出 #2

No

说明/提示

限制

  • 1≤K≤N≤181 \leq K \leq N \leq 18
  • 所有输入值均为整数

样例解释 1

将 PP 用二进制表示为 P=(000,001,011,010,110,111,101,100)P=(000,001,011,010,110,111,101,100)。例如 P1=001,P2=011P_1=001,P_2=011,它们恰好有 11 位不同,因此对于 i=1i=1 条件成立。对所有 ii 也都满足条件。