Nim Game Is XOR Game

Do not start by trying to do bit DP over the chosen $b$. The easy way is to ask which positions are losing.

A position with at most one positive pile is losing. Any valid $b$ would also have at most one positive component, and the XOR of one positive number cannot be $0$.

Now take a position with at least two positive piles. It is winning because it can move to one of those losing positions.

Let

$$X=a_1\oplus a_2\oplus\cdots\oplus a_n.$$

If $X=0$, remove everything: choose $b_i=a_i$ for all $i$. Then the removed XOR is $0$, and the next position is all zero.

If $X\ne 0$, let $p$ be the highest set bit of $X$. Pick an index $j$ where $a_j$ has bit $p$ set. Then

$$X\oplus a_j<a_j,$$

because the highest changed bit is cleared. Set

$$b_j=X\oplus a_j,$$

and for every $i\ne j$, set

$$b_i=a_i.$$

The XOR of the removed array is

$$(X\oplus a_j)\oplus\bigoplus_{i\ne j}a_i=(X\oplus a_j)\oplus(X\oplus a_j)=0.$$

Also $b_j<a_j$, so pile $j$ stays positive, and every other pile becomes $0$. The target has exactly one positive pile, so it is losing.

Therefore the losing positions are exactly the arrays with at most one positive element. Nice: the game looks like XOR chaos, then folds into a one-line shape.

Now count Alice's winning first moves. Since all input $a_i$ are positive, if $n=1$ the answer is immediately $0$.

Assume $n\ge 2$. A winning move must leave either zero positive piles or exactly one positive pile.

The all-zero target has $b_i=a_i$ for all $i$, so it is legal exactly when

$$X=0.$$

This contributes $1$ move if $X=0$.

For a target where only pile $j$ remains positive, all other piles must be fully removed:

$$b_i=a_i \quad (i\ne j).$$

The value of $b_j$ is forced by the XOR condition:

$$b_j=\bigoplus_{i\ne j}a_i=X\oplus a_j.$$

For pile $j$ to remain positive, we need

$$b_j<a_j.$$

That is exactly

$$X\oplus a_j<a_j.$$

For each such index $j$, there is exactly one winning move. If the inequality fails, no move with only pile $j$ positive exists.

So for $n\ge 2$,

$$\text{answer}=[X=0]+\#\{j:X\oplus a_j<a_j\}.$$

The answer is at most $n+1$, but we still print it modulo $998244353$ because the statement asks for it.

Complexity is $O(n)$ per test case and $O(n)$ memory to store the array. The sum of $n$ is $10^6$, so this is comfortably inside the limits.