[ARC138D] Differ by K bits
题意翻译
给出两个正整数 $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`。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc138/tasks/arc138_d
整数 $ N,K $ が与えられます. $ (0,1,\cdots,2^N-1) $ の順列 $ P=(P_0,P_1,\cdots,P_{2^N-1}) $ であって,以下の条件を満たすものが存在するか判定し, また存在するなら一つ構成してください.$ P $ の添字が $ 0 $ から始まることに注意してください.
- すべての $ i $ ($ 0\ \leq\ i\ \leq\ 2^N-1 $) について,$ P_i $ と $ P_{i+1\ \mod\ 2^N} $ は $ 2 $ 進表記でちょうど $ K $ 桁だけ異なる. なお,比較の際はどちらも leading $ 0 $'s を補って $ N $ 桁に揃えた上で比較する.
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる.
> $ N $ $ K $
输出格式
条件を満たす $ P $ が存在しない場合,`No` と出力せよ. 存在する場合,以下の形式で答えを出力せよ.
> Yes $ P_0 $ $ P_1 $ $ \cdots $ $ P_{2^N-1} $
条件を満たす解が複数存在する場合,どれを出力しても正解とみなされる.
输入输出样例
输入样例 #1
3 1
输出样例 #1
Yes
0 1 3 2 6 7 5 4
输入样例 #2
2 2
输出样例 #2
No
说明
### 制約
- $ 1\ \leq\ K\ \leq\ N\ \leq\ 18 $
- 入力される値はすべて整数
### Sample Explanation 1
$ P $ を $ 2 $ 進表記で書くと,$ P=(000,001,011,010,110,111,101,100) $ です. 例えば $ P_1=001,P_2=011 $ なので,これらはちょうど $ 1 $ 桁だけ異なっており,$ i=1 $ について条件が成立していることが確認できます. 同様に,すべての $ i $ についても条件を満たしています.