Universal Cup Judging System

Universal Cup

実行時間制限: 1.5 s メモリ制限: 512 MB 満点: 100
統計

非負整数の集合 $S$ について、$S$ のすべての要素の排他的論理和(XOR)が集合 $S$ 自身に含まれないとき、その集合を XOR排他的(XOR-excluding) であると呼びます。

最初は空である集合 $A$ に対し、$n$ 個の相異なる正の要素 $a_i$ を1つずつ追加していきます。各追加の後に、$A$ の XOR排他的な部分集合の個数を求めてください。

答えは非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。

入力

入力の1行目には、追加する要素の個数を表す単一の整数 $n$ が与えられます。

続く $n$ 行にはそれぞれ、集合に追加する $i$ 番目の要素を表す単一の整数 $a_i$ が与えられます。

出力

$n$ 行出力してください。$i$ 行目には、最初の $i$ 個の要素を追加した後の $A$ の XOR排他的な部分集合の個数を $10^9 + 7$ で割った余りを出力してください。

制約

  • $1 \le n \le 2 \cdot 10^5$,
  • $1 \le a_i \le 2^{60} - 1$,
  • すべての $a_i$ は相異なる。

入力例 1

5
1
2
3
4
5
1
2
5
11
22

注記

$1$ を追加した後、唯一の XOR排他的な部分集合は $\{\}$ です(空集合の XOR は $0$ に等しいです)。

$2$ を追加した後、XOR排他的な部分集合は $\{\}$ と $\{1, 2\}$(その XOR は $3$ に等しい)です。

$3$ を追加した後、XOR排他的な部分集合は $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$, $\{1, 2, 3\}$ です。

$4$ を追加した後、XOR排他的な部分集合は $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$, $\{2, 3, 4\}$ です。$\{1, 2, 3, 4\}$ の XOR は $3$ に等しいため、XOR排他的ではないことに注意してください。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.