問題一覧 > 通常問題

No.1493 隣接xor

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 67
作問者 : penguinmanpenguinman / テスター : noiminoimi kaagekaage
16 ProblemId : 6190 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-07 23:42:57

問題文

長さ $N$ の非負整数列 $A$ が与えられます。$A$ に対して以下の操作を $0$ 回以上繰り返すことで得られる数列は何種類ありますか?

  • 隣接した $2$ 要素を削除し、それらの排他的論理和で置き換える。この操作は $A$ の長さが $2$ 以上である時にのみ行える。

答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを求めてください。

入力

\(N\)
\(A_1\) \(A_2\) \(\ldots\) \(A_N\)

  • $1\leq N\leq 2\times 10^5$
  • $0\leq A_i\lt 2^{30}$
  • 入力は全て整数

出力

種類数を $10^9+7$ で割った余りを $1$ 行に出力してください。

サンプル

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

操作の結果得られる数列は、$(1,\ 3,\ 2),\ (2,\ 2),\ (1,\ 1),\ (0)$ の $4$ 種類です。

サンプル2
入力
4
1 4 4 2
出力
7
サンプル3
入力
10
8 2 0 9 1 3 2 4 9 10
出力
360

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