No.1228 I hate XOR Matching
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 42
作問者 :
tyawanmusi
/ テスター :
opt
タグ : / 解いたユーザー数 42
作問者 :
tyawanmusi
/ テスター :
opt
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。