Universal Cup Judging System

Universal Cup

Time Limit: 1.5 s Memory Limit: 512 MB Total points: 100
Statistics

如果一個非負整數集合 $S$ 中所有元素的互斥或和(XOR)不在集合 $S$ 本身之中,我們就稱集合 $S$ 是 異或排斥(XOR-excluding) 的。

給定一個初始為空的集合 $A$,我們依序將 $n$ 個互不相同的正整數元素 $a_i$ 逐一加入其中。每次加入後,請求出 $A$ 的異或排斥子集的數量。

由於答案可能非常大,請輸出答案對 $10^9 + 7$ 取模後的結果。

輸入格式

輸入的第一行包含一個整數 $n$ —— 要加入的元素數量。

接下來的 $n$ 行,每行包含一個整數 $a_i$ —— 要加入集合的第 $i$ 個元素。

輸出格式

輸出 $n$ 行。在第 $i$ 行,輸出加入前 $i$ 個元素後,$A$ 的異或排斥子集數量對 $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$ 之後,唯一的異或排斥子集是 $\{\}$(空集的互斥或和等於 $0$)。

加入 $2$ 之後,異或排斥子集有 $\{\}$ 和 $\{1, 2\}$(其互斥或和等於 $3$)。

加入 $3$ 之後,異或排斥子集有 $\{\}$、$\{1, 2\}$、$\{1, 3\}$、$\{2, 3\}$ 和 $\{1, 2, 3\}$。

加入 $4$ 之後,異或排斥子集有 $\{\}$、$\{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\}$ 的互斥或和等於 $3$,因此它不是異或排斥的。

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.