大和証券プログラミングコンテスト2022 Spring (AtCoder Regular Contest 138)
D
Differ by K bits
AtCoder
⌀ 2083
原题
← CE →
翻译中…

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.

翻译中…

样例

Input #1
3 1
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$.
Input #2
2 2
Output #2
No
题目信息
题号
arc138_d
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。