問題一覧 > 通常問題

No.1228 I hate XOR Matching

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 32
作問者 : tyawanmusityawanmusi / テスター : optopt
2 ProblemId : 4613 / 出題時の順位表
問題文最終更新日: 2020-09-11 21:47:20

元ネタ

XOR Matching
面白い問題です。

問題文

以下の条件を満たす整数列 $a = \{a_1,a_2,\dots , a_N\}$ が存在するならば $1$ つ構築してください。

  • $1 \le N \le 40$
  • $0 \le a_i < 2^{20}$
  • 各 $i$ $(0 \le i < 2^{20})$ は高々 $2$ 回しか $a$ に現れない
  • $a$ の空でない部分列 $2^N-1$ 個のうち、部分列の bitwise XOR が $K$ であるものがちょうど $X$ 個ある。

制約

  • 入力は全て整数
  • $0 \le K < 2^{20}$
  • $0 \le X \le 10^9$

入力

$K\ X$

$1$ 行で $K,X$ が空白区切りで与えられます。

出力

Yes / No
$N$
$a_1\ a_2\ \dots\ a_N$

条件を満たす数列が存在しない場合はNoを $1$ 行に出力してください。
そうではない場合、$1$ 行にYesを出力したあとに $2$ 行出力してください。
$2$ 行目には数列の長さ $N$ を、$3$ 行目には数列 $a$ を空白区切りで出力してください。
最後に改行してください。

上記の指定に沿わない出力がなされた時の判定は未定義です。

サンプル

サンプル1
入力
3 2
出力
Yes
2
0 3

$a$ の部分列を列挙すると $(0,3),(0),(3)$ となります。
このうち、部分列の $\mathrm{xor}$ が $3$ であるものは $(0,3),(3)$ と $2$ 個であるため、条件を満たしています。

サンプル2
入力
5 8
出力
Yes
4
5 0 0 5

$(0,5)$ は $2$ 個あります。

サンプル3
入力
0 3
出力
Yes
3
0 1 1
サンプル4
入力
0 2
出力
No

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。