L - Range XOR X Count
Milk
2
s
1024
MB
100
点
問題文
整数 $K, X$ が与えられます。長さ $N$ の整数列 $A = (A_1, A_2, \ldots, A_N)$ であって、次の条件をすべて満たすものを出力してください。ただし、この制約下で条件を満たす整数列が必ず存在することが証明できます。
- $1 \leq N \leq 10^4$
- $0 \leq A_i < 2^{60}$
- $A$ のすべての要素は相異なる
- $1 \leq l \leq r \leq N$ を満たす整数組 $(l, r)$ であって、$A_l \oplus A_{l+1} \oplus \cdots \oplus A_r = X$ を満たすものがちょうど $K$ 組存在する。ただし、$\oplus$ は bitwise XOR を表す。
bitwise XORとは？
非負整数 $a, b$ の bitwise XOR $a \oplus b$ は、以下のように定義される非負整数です。
- $a \oplus b$ を $2$ 進法表記した際の $2^k$ $(k \geq 0)$ の位の数は、$a, b$ を $2$ 進法表記した際の $2^k$ の位のうち一方のみが $1$ であれば $1$ 、そうでなければ $0$ である
例えば $3 \oplus 5 = 6$ となります。
制約
- $1 \leq K \leq 10^{5}$
- $0 \leq X < 2^{60}$
- 入力はすべて整数である
部分点
set1$(30$ 点$)$： $X=0$all$(70$ 点$)$：追加の制約はない
入力
入力は以下の形式で標準入力から与えられます。
$K$ $X$
出力
$2$ 行出力してください。
$1$ 行目に出力する整数列の長さ $N$ を出力してください。
$2$ 行目に条件を満たす整数列 $A$ を空白区切りで出力してください。
入力例 1
1 0
出力例 1
4
1 2 3 4
$1 \leq l \leq r \leq N$ を満たす整数組 $(l, r)$ であって、$A_l \oplus A_{l+1} \oplus \cdots \oplus A_r = X$ を満たすものは $(l, r) = (1, 3)$ のみです。
この入力例は部分点 set1 の制約を満たします。
入力例 2
4 2024
出力例 2
13
1167 374 954 1316 1884 72 563 1959 640 90 1195 1831 1086