Universal Cup Judging System

Universal Cup

時間限制: 1.5 s 記憶體限制: 512 MB 總分: 100
统计

נאמר שקבוצה $S$ של מספרים שלמים אי-שליליים היא מוציאת-XOR (XOR-excluding) אם ה-XOR של כל האיברים ב-$S$ אינו נמצא בקבוצה $S$ עצמה.

בהינתן קבוצה $A$ שהיא ריקה בהתחלה, אנו מוסיפים לה $n$ איברים חיוביים שונים $a_i$ בזה אחר זה. לאחר כל הוספה, מצאו את מספר תתי-הקבוצות מוציאות ה-XOR של $A$.

מכיוון שהתשובה עלולה להיות גדולה מאוד, הדפיסו אותה מודולו $10^9 + 7$.

קלט

השורה הראשונה של הקלט מכילה מספר שלם יחיד $n$ — מספר האיברים שיש להוסיף.

$n$ השורות הבאות מכילות כל אחת מספר שלם יחיד $a_i$ — האיבר ה-$i$ שיש להוסיף לקבוצה.

פלט

הדפיסו $n$ שורות. בשורה ה-$i$, הדפיסו את מספר תתי-הקבוצות מוציאות ה-XOR של $A$ לאחר הוספת $i$ האיברים הראשונים, מודולו $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.