201383: [AtCoder]ARC138 D - Differ by K bits

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $700$ points

Problem Statement

You are given integers $N$ and $K$. Determine whether there exists a permutation $P=(P_0,P_1,\cdots,P_{2^N-1})$ of $(0,1,\cdots,2^N-1)$ satisfying the condition below, and construct one such sequence if it exists. Note that $P$ is $0$-indexed.

  • For every $i$ ($0 \leq i \leq 2^N-1$), $P_i$ and $P_{i+1 \mod 2^N}$ differ by exactly $K$ bits in binary representation. The comparison is made after zero-padding both integers to $N$ bits.

Constraints

  • $1 \leq K \leq N \leq 18$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $K$

Output

If there is no $P$ satisfying the condition, print No. If there is such a $P$, print it in the following format:

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

If there are multiple solutions satisfying the condition, printing any of them will be accepted.


Sample Input 1

3 1

Sample Output 1

Yes
0 1 3 2 6 7 5 4

Here, we have $P=(000,001,011,010,110,111,101,100)$ in binary representation.

We can see that $P_1=001$ and $P_2=011$, for example, differ by exactly $1$ bit, satisfying the condition for $i=1$. The same goes for every $i$.


Sample Input 2

2 2

Sample Output 2

No

Input

题意翻译

给出两个正整数 $N,K$,构造排列 $P_0,P_1,...,P_{2^N-1}$ 使得对于所以 $i(0\le i\le 2^N-1)$,$P_i$ 和 $P_{i+1}$ 的二进制前 $N$ 位正好相差 $K$ 位。另外,比较的两者都要用 $0$ 补齐到至少 $N$ 位。 --- 输入一行两个正整数 $N,K$。 若有合法的构造,第一行输出 `Yes`,第二行输出 $2^N$ 个数,表示你构造的 $P_0,P_1,...,P_{2^N-1}$,给出任意一组构造即可。 否则输出一行 `No`。

加入题单

上一题 下一题 算法标签: