No.183 たのしい排他的論理和(EASY)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 147
作問者 : 紙ぺーぱー紙ぺーぱー

2 ProblemId : 470 / 出題時の順位表

問題文

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 5000)$が与えられる。
2行目にスイッチに書かれた整数$A_i(1 \le A_i \le 16384(2^{14}))$が空白区切りで与えられる。

出力

作ることができる整数の総数を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種類しか作れない場合もあります。

提出ページヘ