問題一覧 > 通常問題

No.184 たのしい排他的論理和(HARD)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 147
作問者 : 紙ぺーぱー紙ぺーぱー
14 ProblemId : 481 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:41

問題文

頭脳派おたくのkamipeipaa君は勉強を続けています。kamipeipaa君は復習を欠かしません。今日は以下の問題を解いています。

$N$個のスイッチを発見した。$i$番目のスイッチには$A_i$という整数が書かれている。あなたは$i$番目のスイッチを押すことで、ある整数$X$に対して
$X = X \oplus A_i$
という操作を行うことができる。ただし$\oplus$とはビットXORの記号である(参考)。
一度押したスイッチは二度と使用することはできない。
$X$ははじめ$0$である。
あなたが作ることができる整数は何種類あるか。

kamipeipaa君はこの問題の制約を厳しくしても解くことができることに気づいたので解くことにしました。あなたも解いてあげてください。

入力

$N$
$A_1$ $A_2$ ... $A_N$

1行目にスイッチの数$N(1 \le N \le 10^{5})$が与えられる。
2行目にスイッチに書かれた整数$A_i(1 \le A_i \le 1152921504606846976(2^{60}))$が空白区切りで与えられる。

出力

作ることができる整数の総数を1行で出力しなさい。改行を忘れないこと。

サンプル

サンプル1
入力
2
1 2 
出力
4

$0 = 0$
$1 = 0 \oplus 1$
$2 = 0 \oplus 2$
$3 = 0 \oplus 1 \oplus 2$
の4種類の値を作ることができます。

サンプル2
入力
6
1 1 4 5 1 4
出力
4

6つ整数が与えられても4種類しか作れない場合もあります。

サンプル3
入力
32
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648
出力
4294967296

入力や出力が32bit符号付整数で表せない場合も存在することに注意してください。

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