https://betrue12.hateblo.jp/entry/2019/05/20/213302

解法

結論を書いてしまうと、以下のような数列がもし作れれば答えになります。

f:id:betrue12:20190520210750p:plain

アイデアとしては、まず $K$ を挟んで $K$ 以外の数字を鏡写しに並べます。こうすることで $K$ 以外のどの数字を選んでも、2つの位置の間（両端を含む）にあるものは「 $K$ 1個と、同じ数字の2個ペアたち」となり、同じ数字のペアはXORで打ち消し合うので必ずXORの値が $K$ になります。

あとは $K$ 同士のXORも $K$ にならないといけませんが… $M \ge 2$ の場合は もう1つの $K$ を端に置くことで間にある値のXORが必ず $K$ になります。これは、

$a$ を非負整数として、 $4a, 4a+1, 4a+2, 4a+3$ のXORを取ると必ず0になる

という性質によるものです。この性質は以前のABCにも登場しましたね。

$M \ge 2$ であれば $0, 1, ..., 2^{M}-1$ は上記のような4つ組のグループに分けられるので、そのXORは0になります。今回 $K$ と $K$ の間（両端を含む）にある値はこれらの値1つずつと $K$ 1個だけが余っているので、そのXORは $K$ になります。

ということで、 $K \le 2^{M}-1$ かつ $M \ge 2$ のときは答えを求めることができました。あとは残りのケースを考慮します。

もし $K \ge 2^{M}$ である場合には、 $K$ の最上位ビットは $2^{M}$ の位以上になり、 $0, 1, ..., 2^{M}-1$ の値をどうXORで組み合わせてもこのビットを作ることはできません。つまり、この場合は構成不可能です。

$M = 1$ の場合は入出力例に示されている通りなので、これをそのまま埋め込んでしまえばよいです。 $M = 0$ も実は制約に含まれていますが、この場合は 0 0 しか作れないので $K=0$ の場合だけ答えが存在します（考慮していなくても $M \ge 2$ と同じ実装で正しく処理できることが多いでしょう）。

ACコード

Submission #5462845 - AtCoder Beginner Contest 126