[ARC146C] Even XOR
配点 : 点
問題文
以上 未満の非負整数からなる集合 のうち、以下の条件を満たすものの個数を で割ったあまりを出力してください。
- の空でない部分集合 は以下のどちらかを満たす。- の要素数が奇数
- の全要素の が でない
- の要素数が奇数
- の全要素の が でない
$\mathrm{XOR}$ とは
非負整数 $A, B$ のビット単位 $\mathrm{XOR}$ 、$A \oplus B$ は、以下のように定義されます。
- $A \oplus B$ を二進表記した際の $2^k$ ($k \geq 0$) の位の数は、$A, B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。
一般に k 個の整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
制約
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
2
15
や や は条件を満たします。
は条件を満たしません。
なぜなら、 は部分集合 が要素数が偶数であり、全要素の が であるからです。
146
743874490