大和証券プログラミングコンテスト2022 Spring (AtCoder Regular Contest 138)
翻译中…
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
题目信息
题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。