atcoder#ABC278H. [ABC278Ex] make 1
[ABC278Ex] make 1
配点 : 点
問題文
次の条件を満たす非負整数列 を 良い数列 と呼びます。
- の(連続とは限らない)非空な部分列 であって、 のすべての要素のビットごとの xor が であるようなものが存在する。
空の数列 、および 以上 未満の整数が 1 つずつ書かれた 枚のカードがあります。 あなたは次の操作を が良い数列になるまで繰り返します。
- カードを 1 枚自由に選び、カードに書かれている数を の末尾に追加する。そして選んだカードを食べる。(食べたカードはその後選ぶことはできない)
操作後の としてあり得る数列のうち長さが であるものは何種類ありますか? 答えを で出力してください。
ビットごとの xor とは?
非負整数 A, B のビット単位 xor 、A \oplus B は、以下のように定義されます。- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- は整数
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
2 2
5
操作後の としてあり得る数列のうち長さが であるものは次の 種類です。
2022 1119
293184537
200000 10000000
383948354