以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Problem L
XOR Operations
Time limit: 2 seconds
You are given n integers a1, a2, . . . , an. You have a sequence of n integers B = (b1, b2, . . . , bn) which initially are all
zeroes.
In one operation, you choose two different indices i and j, then simultaneously
• replace bi with bi ⊕ai ⊕aj, and
• replace bj with bj ⊕ai ⊕aj.
Note that ⊕represents the bitwise XOR operation, which returns an integer whose binary representation has a 1 in
each bit position for which the corresponding bits of either but not both operands are 1. For example, 3 ⊕10 = 9
because (0011)2 ⊕(1010)2 = (1001)2.
You want to compute the number of different possible sequences B you can obtain after performing zero or more
operations. Since this number might be huge, calculate this number modulo 998 244 353.
Two sequences of length n are considered different if and only if there exists an index i (1 ≤i ≤n) such that the i-th
element of one sequence differs from the i-th element of the other sequence.
Input
The first line of input contains one integer n (2 ≤n ≤200 000). The second line contains n integers a1, a2, . . . , an
(0 ≤ai < 230 for all i).
Output
Output an integer representing the number of different possible sequences B you can obtain after performing zero or
more operations modulo 998 244 353.
Sample Input #1 Sample Output #1
3 4
1 2 1
Explanation for the sample input/output #1
Starting from B = (0, 0, 0), we can obtain the following two sequences B:
• Perform the operation with i = 1 and j = 2. We will have B = (3, 3, 0).
• After that, perform the operation with i = 2 and j = 3. We will have B = (3, 0, 3).
Starting from B = (0, 0, 0), we can also obtain the following sequence B:
• Perform the operation with i = 2 and j = 3. We will have B = (0, 3, 3).
ICPC Asia Pacific Championship 2024 Problem L: XOR Operations
It can be shown that (0, 0, 0), (3, 3, 0), (3, 0, 3), and (0, 3, 3) are the only possible sequences B you can obtain.
Therefore, the answer is 4.
Sample Input #2 Sample Output #2
4 1
852415 852415 852415 852415
ICPC Asia Pacific Championship 2024 Problem L: XOR Operations