XOR Operations (Problem L, The 2024 ICPC Asia Pacific Championship, 2024)
Time limit: 2 sec
Author: Prabowo Djonatan, Muhammad Ayaz Dzulfikar

# Problem Statement

You are given $n$ integers $a_1, a_2, \ldots, a_n$. You have a sequence of $n$ integers $B = (b_1, b_2, \ldots, b_n)$ which initially are all zeroes.

In one operation, you choose two different indices $i$ and $j$, then simultaneously

- replace $b_i$ with $b_i \oplus a_i \oplus a_j$, and
- replace $b_j$ with $b_j \oplus a_i \oplus a_j$.

Note that $\oplus$ 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 \oplus 10 = 9$ because $(0011)_2 \oplus (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 $998244353$.

Two sequences of length $n$ are considered different if and only if there exists an index $i$ ($1 \le i \le 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 \le n \le 200000$). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^{30}$ 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 $998244353$.

# Sample Input #1
```
3
1 2 1
```
# Sample Output #1
```
4
```
### 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)$.

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
```
4
852415 852415 852415 852415
```
# Sample Output #2
```
1
```

Sample inputs:
3
1 2 1

4
852415 852415 852415 852415

Sample outputs:
4

1

# Solution Analysis
Analysis author: Mitsuru Kusumoto

As a preprocessing step, let us replace each input integer $a_i$ with $2a_i + 1$. This alteration does not affect the result; however, it proves to be useful for subsequent calculations.

A $d$-bit integer can be represented by a row vector in $(\mathbb{Z}/2\mathbb{Z})^d$. For an input $a_i$, let us denote the corresponding row vector in $(\mathbb{Z}/2\mathbb{Z})^d$ by $\vec{a}_i$. The XOR operation $a_i \oplus a_j$ corresponds to the addition $\vec{a}_i + \vec{a}_j$ in $(\mathbb{Z}/2\mathbb{Z})^d$.

Similarly, the sequence $B$ can be represented as $n$ row vectors in $(\mathbb{Z}/2\mathbb{Z})^d$. Now, the operation for indices  
$i$ and $j$ ($b_i \leftarrow b_i \oplus a_i \oplus a_j$ and $b_j \leftarrow b_j \oplus a_i \oplus a_j$) can be considered as an addition of $(\vec{0} \ldots, \vec{0}, \vec{a}_i + \vec{a}_j^{\ i}, \vec{0}, \ldots, \vec{0})$ to $B$. Let us denote this row vector by $\vec{v}_{i,j}$. Note that the dimension of $\vec{v}_{i,j}$ is $nd$.  
There are $\binom{n}{2}$ choices for $i$ and $j$. The solution to this problem is the number of elements in the space spanned by the vectors $\vec{v}_{i,j}$. Let $M$ be a $\binom{n}{2} \times (nd)$ matrix such that each row corresponds to a vector $\vec{v}_{i,j}$.  
The solution is equal to $2^{\text{rank}(M)}$. Thus, in summary, we only need to determine the rank of $M$.

To investigate the rank of $M$, for $k \ge 2$, let

$$
D_k = \begin{bmatrix}
\vec{a}_1 + \vec{a}_k \\
\quad\vec{a}_2 + \vec{a}_k \\
\quad\quad\ddots \\
\quad\quad\quad\vec{a}_{k-1} + \vec{a}_k
\end{bmatrix},
\quad
F_k = \begin{bmatrix}
\vec{a}_1 + \vec{a}_k \\
\vec{a}_2 + \vec{a}_k \\
\vdots \\
\vec{a}_{k-1} + \vec{a}_k
\end{bmatrix},
$$


and $R_k$ be an $(k-1) \times (nd)$ matrix $[D_k \mid F_k \mid O]$. Also, let $M_k$ be a matrix formed by stacking matrices $R_2, R_3, \ldots, R_k$ vertically. The matrix $M$ as described above is equivalent to $M_n$. Without loss of generality, we can assume that $s$ row vectors $\vec{a}_1, \ldots, \vec{a}_s$ are linearly independent, and other vectors can be expressed as the sum of a subset of $\vec{a}_1, \ldots, \vec{a}_s$.

### Observation L.1.
$\text{rank}(M_s) = \binom{s}{2}$.

**Proof.** Suppose that $\sum_{(i,j) \in C} \vec{v}_{i,j} = 0$ for some set of indices $C \subseteq \{(i,j) \mid 1 \le i < j \le s\}$. Let us examine the first $d$ elements of the vector $\sum_{(i,j) \in C} \vec{v}_{i,j}$. In particular, $\sum_{(1,j) \in C} (\vec{a}_1 + \vec{a}_j) = \vec{0}$ must hold. Because $\vec{a}_1, \ldots, \vec{a}_s$ are linearly independent, $C$ cannot contain any element of the form $(1,j)$ for $j = 2, \ldots, s$. With the same arguments applied to other elements, we can deduce that $C$ must be empty. This means that the row vectors in $M_s$ are linearly independent, and therefore $\text{rank}(M_s) = \binom{s}{2}$.

### Observation L.2.
For $k > s$, $\text{rank}(M_k) = \text{rank}(M_{k-1}) + s - 1$.

From Observations L.1 and L.2, we can conclude that the rank of $M$ is $\binom{s}{2} + (n - s)(s - 1)$. Since the computation of $s$, the number of linearly independent vectors, can be performed in $O(nd)$ time, the runtime is $O(nd)$. (In this problem, $d = 31$.) The remaining part is the outline of the proof for Observation L.2.

**Proof.** First, we can show that the rank of $F_k$ is $s - 1$. Because the rows of $F_k$ are linear combinations of $\vec{a}_1, \ldots, \vec{a}_s$, $\text{rank}(F_k) \le s$. The rank can be further bounded by $s - 1$ because any combination of rows in $F_k$ always contains an even number of $\vec{a}_1, \ldots, \vec{a}_s$. (Here, we utilized the result of the preprocessing, that $\vec{a}_{s+1}, \ldots, \vec{a}_k$ are represented by an **odd** number of sums of the basis $\vec{a}_1, \ldots, \vec{a}_s$.) Also, without loss of generality, we can assume that $\vec{a}_k = \vec{a}_1 + \cdots + \vec{a}_t$, where $t \ge 1$ is an odd integer. Then, the $s - 1$ vectors $\vec{a}_2 + \vec{a}_k, \vec{a}_3 + \vec{a}_k, \ldots, \vec{a}_s + \vec{a}_k$ are linearly independent. From this, we can conclude that $\text{rank}(F_k) = s - 1$.

Next, since the matrix $M_k$ has the form

$$
M_k = \begin{bmatrix}
M_{k-1} & O \\
D_k & F_k
\end{bmatrix},
$$

we can say that $\text{rank}(M_k) \ge \text{rank}(M_{k-1}) + s - 1$. To show that the inequality “$\ge$” is actually an equality, we need to establish that the elements of $D_k$ do not affect the rank of $M_k$. Suppose that there exists a subset $C \subseteq \{1, \ldots, k - 1\}$ such that $\sum_{i \in C} (\vec{a}_i + \vec{a}_k) = \vec{0}$. That is, $C$ represents the indices of rows in $F_k$ whose sum equals $\vec{0}$. For our purposes, it suffices to show that there always exists a subset $C' \subseteq \{(i,j) \mid 1 \le i < j < k\}$ such that $\sum_{i \in C} \vec{v}_{i,k} = \sum_{(i,j) \in C'} \vec{v}_{i,j}$.

When $|C|$ is odd, because $\vec{a}_k = \sum_{i \in C} \vec{a}_i$, $C' = \{(i,j) \mid i, j \in C, i < j\}$ satisfies the condition. Meanwhile, when $|C|$ is even, because $\sum_{i \in C} \vec{a}_i = \vec{0}$, a set $C'$ constructed from $\{1, \ldots, t\} \times C$ satisfies the condition. This concludes the statement of the observation.

Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to tcframe format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}