Universal Cup Judging System

Universal Cup

Süre Sınırı: 1.5 s Bellek Sınırı: 512 MB Toplam puan: 100
İstatistikler

음이 아닌 정수로 이루어진 집합 $S$의 모든 원소의 배타적 논리합(XOR)이 집합 $S$ 자체에 속하지 않을 때, 집합 $S$를 XOR 배제(XOR-excluding) 집합이라고 부릅니다.

처음에 비어 있는 집합 $A$가 주어지고, 여기에 $n$개의 서로 다른 양의 원소 $a_i$를 하나씩 차례대로 추가합니다. 원소를 하나 추가할 때마다, $A$의 부분집합 중 XOR 배제 집합의 개수를 구하세요.

정답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력합니다.

입력

입력의 첫 번째 줄에는 추가할 원소의 개수를 나타내는 정수 $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.