Peanuts
Contest: Codeforces Round 983 (Div. 2)
Difficulty rating: 2700
Tags: combinatorics, dp, games, math

Having the magical beanstalk, Jack has been gathering a lot of peanuts lately. Eventually, he has obtained $$$n$$$ pockets of peanuts, conveniently numbered $$$1$$$ to $$$n$$$ from left to right. The $$$i$$$-th pocket has $$$a_i$$$ peanuts.

Jack and his childhood friend Alice decide to play a game around the peanuts. First, Alice divides the pockets into some boxes; each box will have a non-zero number of consecutive pockets, and each pocket will, obviously, belong to exactly one box. At the same time, Alice does not change the order of the boxes, that is, the boxes are numbered in ascending order of the indices of the pockets in them.

After that, Alice and Jack will take turns alternately, with Alice going first.

At each turn, the current player will remove a positive number of peanuts from exactly one pocket which belongs to the leftmost non-empty box (i.e., the leftmost box containing at least one non-empty pocket). In other words, if we number the boxes from left to right, then each player can only pick peanuts from the pocket in the $$$j$$$-th box ($$$j \ge 2$$$) only if the $$$(j - 1)$$$-th box has no peanuts left. The player who cannot make a valid move loses.

Alice is sure she will win since she has the advantage of dividing the pockets into boxes herself. Thus, she wanted to know how many ways there are for her to divide the peanuts into boxes at the start of the game so that she will win, assuming both players play optimally. Can you help her with the calculation?

As the result can be very large, output it modulo $$$998\,244\,353$$$.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the number of pockets.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the number of peanuts in each pocket.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output a single integer — the number of ways for Alice to divide the pockets into boxes at the start of the game to guarantee her win, assuming both players play optimally, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the only way for Alice to win is to divide the pockets into two boxes as follows: $$$([1, 2], [3])$$$ (the first box contains the first two pockets and the second box contains the third pocket). Alice wins by taking both peanuts from the second pocket, leaving Jack with $$$([1], [3])$$$. Jack is forced to take the only peanut left in the first box, which allows Alice to take the remaining ones in the second box.

In the second test case, the winning divisions for Alice are $$$([1], [2, 3, 1])$$$, $$$([1, 2, 3, 1])$$$, $$$([1, 2], [3], [1])$$$, and $$$([1, 2], [3, 1])$$$.

In the third test case, Alice always wins no matter how she divides the pockets into boxes.

In the fourth test case, Alice always loses no matter how she divides the pockets into boxes.

Example input:
5
3
1 2 3
4
1 2 3 1
5
1 1 1 1 1
2
1 1
10
1 2 3 4 5 6 7 8 9 10

Example output:
1
4
16
0
205

Editorial:
Let's get the trivial case out of the way: If the peanut pockets always contain $$$1$$$ nut each, then partitioning the pockets doesn't affect the game's outcome at all:
• Alice will always win if $$$n$$$ is odd, and there are $$$2^{n-1}$$$ ways to partition $$$n$$$ pockets.
• Jack will always win if $$$n$$$ is even.
Proof for the trivial case is, indeed, trivial.
For the main problem, we see that this is a derivative of a game of Nim. To be exact, each box is a vanilla Nim game. To determine the winner of a vanilla Nim game when both players play optimally is trivial — if not for you, I strongly suggest reading about the game and the Sprague-Grundy theorem before continuing.
In short, the Nim-sum of a Nim game is the xor sum of all values presented, and if that value is at least $$$1$$$, the first player will win if they play optimally.
The original game of this problem is a series of consecutive Nim games, with the loser of the previous game becoming the first player of the next game. Clearly, trying to win all the boxes isn't a correct approach — one of the simplest counterexamples is a partition with two boxes, both with the first player winning if played optimally, so of course if the first player "wins" the first box, they immediately lose the second one and thus lose the whole game.
In short, sometimes, tactically "losing" some boxes might be required. But how to know which player would lose if they both aimed for it?
Now, introducing the "mirrored" version of a Nim game — a Misère Nim game, where the winning condition is the original Nim game's losing condition.
If the peanut pockets always contain $$$1$$$ nut each, then the winner of a Misère Nim game can be easily declared by the parity of $$$n$$$. Otherwise, the winner of a Misère Nim game can be decided using the same nimber used in a regular Nim game: if the nimber is not $$$0$$$, the first player wins both the original and the Misère version; otherwise, the second player wins — the optimal strategies to acquire such outcome have the exact mirror intents of those in a regular Nim game.
Also, surpassing the leading $$$1$$$s in array $$$a$$$, both Alice and Jack have the rights to tactically lose. Thus, any of them would win the game if and only if they could win the first box containing non-trivial pockets (here defined as pockets with more than $$$1$$$ nut, we'll call a box having at least one non-trivial pocket a non-trivial box) if both play optimally until there — as proven above, if they could theoretically win it, they could also tactically lose it, thus they would have full control of the game, and they could make a decision in accordance with whatever partition coming next in the remaining pockets.
We'll denote $$$l$$$ as the number of trivial pockets (i.e. pockets with $$$1$$$ nut each) standing at the left side of array $$$a$$$, i.e., the $$$(l+1)^{th}$$$ pocket will be the leftmost one to have more than $$$1$$$ nut. We'll consider all possible options for first boxes containing non-trivial pockets, and thus we'll iterate $$$r$$$ in range $$$[l+1, n]$$$:
• First, we denote $$$P(r)$$$ as the xor sum of all elements of the prefix of array $$$a$$$ up until the $$$r^{th}$$$ element. This value will determine how much control Alice would have.
• If $$$P(r) = 0$$$, Alice will lose in all cases with the first non-trivial box ending at $$$r$$$. Proof is simple: if this box has an even amount of $$$1$$$s before it, obviously Alice will be the starting player of a game with nimber of $$$0$$$ and thus cannot control it to her will; and if the amount of preceding $$$1$$$s is odd, then the first non-trivial box is a game with nimber of $$$1$$$ and Jack as first player, thus Jack retains full control.
• If $$$P(r) = 1$$$, Alice will win in all cases with the first non-trivial box ending at $$$r$$$. Proof is literally the reverse of the above case.
• If $$$P(r) > 1$$$, both Alice and Jack have full control to win it, thus Alice will win if and only if she is the starting player of the game at the first non-trivial box.
So we have the detailed winning condition. Now, towards the maths.
• First, whatever pockets after the first non-trivial box doesn't matter. Thus, for each $$$r$$$, there exists $$$2^{\max(0, n-r-1)}$$$ different partitions of the pockets following the $$$r^{th}$$$ one.
• We don't consider cases with $$$P(r) = 0$$$, obviously.
• If $$$P(r) = 1$$$, all partitions involving only the first $$$l$$$ pockets are allowed. In fact, there are $$$l+1$$$ items here: $$$l$$$ trivial pockets, and the first non-trivial blob always coming last, thus the number of different partitions of the pockets preceding the $$$r^{th}$$$ one in this case is $$$2^l$$$.
• If $$$P(r) > 1$$$, we'll consider all even $$$l_0$$$ in range $$$[0, l]$$$, with $$$l_0$$$ denoting the number of $$$1$$$s not within the first non-trivial box. Clearly, for each $$$l_0$$$, the number of different partitions would be $$$2^{\max(0, l_0-1)}$$$. And since $$$l$$$ is fixed and this process has no relation with $$$r$$$, this value could be pre-calculated. In more details, denoting that value as $$$M$$$, we have $$$M = \sum_{i = 0}^{\lfloor \frac{l0}{2} \rfloor} 2^{\max(0, 2i-1)}$$$.
• All powers of $$$2$$$ could be pre-calculated as well, saving a considerable amount of runtime. All pre-calculations have time complexity in linear order of the maximum size of array $$$a$$$.
Time complexity: $$$\mathcal{O}(n)$$$.