Universal Cup Judging System

Universal Cup

时间限制: 1.5 s 内存限制: 512 MB 总分: 100
统计

Ta nói rằng một tập hợp $S$ gồm các số nguyên không âm là loại trừ XOR (XOR-excluding) nếu tổng XOR của tất cả các phần tử trong $S$ không nằm trong chính tập hợp $S$.

Cho một tập hợp $A$ ban đầu rỗng, ta lần lượt thêm $n$ phần tử nguyên dương phân biệt $a_i$ vào tập hợp từng phần tử một. Sau mỗi lần thêm, hãy tìm số lượng tập con loại trừ XOR của $A$.

Vì đáp án có thể rất lớn, hãy in ra kết quả theo modulo $10^9 + 7$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $n$ — số lượng phần tử cần thêm.

$n$ dòng tiếp theo, mỗi dòng chứa một số nguyên duy nhất $a_i$ — phần tử thứ $i$ được thêm vào tập hợp.

Dữ liệu ra

In ra $n$ dòng. Trên dòng thứ $i$, in ra số lượng tập con loại trừ XOR của $A$ sau khi thêm $i$ phần tử đầu tiên, theo modulo $10^9 + 7$.

Giới hạn

  • $1 \le n \le 2 \cdot 10^5$,
  • $1 \le a_i \le 2^{60} - 1$,
  • tất cả các $a_i$ đều đôi một phân biệt.

Ví dụ 1

5
1
2
3
4
5
1
2
5
11
22

Ghi chú

Sau khi thêm $1$, tập con loại trừ XOR duy nhất là $\{\}$ (tập rỗng có tổng XOR bằng $0$).

Sau khi thêm $2$, các tập con loại trừ XOR là $\{\}$ và $\{1, 2\}$ (có tổng XOR bằng $3$).

Sau khi thêm $3$, các tập con loại trừ XOR là $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ và $\{1, 2, 3\}$.

Sau khi thêm $4$, các tập con loại trừ XOR là $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ và $\{2, 3, 4\}$. Lưu ý rằng $\{1, 2, 3, 4\}$ có tổng XOR bằng $3$, nên nó không phải là tập loại trừ 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.