Zero-XOR Array
Contest: Kotlin Heroes 5: ICPC Round
Difficulty rating: 3400
Tags: *special, dp

You are given an array of integers $$$a$$$ of size $$$n$$$. This array is non-decreasing, i. e. $$$a_1 \le a_2 \le \dots \le a_n$$$.

You have to find arrays of integers $$$b$$$ of size $$$2n - 1$$$, such that:

- $$$b_{2i-1} = a_i$$$ ($$$1 \le i \le n$$$);
- array $$$b$$$ is non-decreasing;
- $$$b_1 \oplus b_2 \oplus \dots \oplus b_{2n-1} = 0$$$ ($$$\oplus$$$ denotes bitwise XOR operation: https://en.wikipedia.org/wiki/Exclusive_or. In Kotlin, it is xor function).

Calculate the number of arrays that meet all the above conditions, modulo $$$998244353$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 17$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers ($$$0 \le a_i \le 2^{60} - 1; a_i \le a_{i+1}$$$) — elements of the array $$$a$$$.

Output format:
Print a single integer — the number of arrays that meet all the above conditions, modulo $$$998244353$$$.

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

Example input:
3
0 1 3

Example output:
2

Example input:
4
0 3 6 7

Example output:
6

Editorial:
Let's reformulate our problem as the following: we need to choose $$$n-1$$$ elements $$$b_i$$$ such that $$$a_i \le b_i \le a_{i + 1}$$$ and $$$b_1 \oplus \dots \oplus b_{n - 1} = a_1 \oplus \dots \oplus a_n$$$. We can solve this problem from the most significant bit to the least significant bit.
On each bit level $$$pw$$$, for each $$$b_i$$$ we have a segment of possible values $$$[l, r]$$$. Let's define the $$$pw$$$-th bit of a value $$$x$$$ as $$$x(pw)$$$. If the $$$l(pw) = r(pw)$$$, we have no choice for $$$b_i$$$ and segment $$$[l, r]$$$ doesn't change. Otherwise, $$$l(pw) = 0$$$ and $$$r(pw) = 1$$$. And we have two choices:
• if we choose $$$b_i(pw) = 0$$$ then the left border $$$l$$$ doesn't change, but the right border $$$r$$$ becomes $$$2^{pw} - 1$$$ (it's not exactly $$$2^{pw} - 1$$$, but since we iterate $$$pw$$$ in descending order we can ignore all bits higher than $$$pw$$$);
• if we choose $$$b_i(pw) = 1$$$ them the right border $$$r$$$ doesn't change, but the left border $$$l$$$ becomes $$$0$$$ (we also ignore all bits higher than $$$pw$$$).
As a result, we can note that the left border is either initial $$$a_i$$$ or $$$0$$$ and the right border is either initial $$$a_{i + 1}$$$ or $$$2^{pw} - 1$$$. It leads us to the bitmask dynamic programming with $$$4$$$ states for each $$$b_i$$$. But even with a broken profile technique, it will be something like $$$O(4^n n \cdot B)$$$ where $$$B$$$ is the number of bits. So let's look further.
Note, that if we meet the state where the left segment is $$$0$$$ and the right is $$$2^{pw} - 1$$$ then this situation is special since we can choose any possible combination of other values of $$$b_j$$$ and counter it with exactly one number in $$$[0, 2^{pw} - 1]$$$ such that XOR of all $$$b_i$$$ will be exactly $$$a_1 \oplus \dots \oplus a_n$$$. So, if we meet this state in at least one $$$b_i$$$ we can explicitly calculate the answer as the product of all segments $$$[l, r]$$$ except this one.
From the other side, if the left border became $$$0$$$ (or the right became $$$2^{pw} - 1$$$) it will persist later and the state will change only to $$$[0, 2^{pw} - 1]$$$ when we choose the opposite step. For example, if for the $$$b_i$$$ we at first chose to set $$$0$$$ (and met the state $$$[l, 2^{pw} - 1]$$$) and if after that we choose more $$$0$$$, the state won't change. Only after choosing $$$1$$$ we'll meet the state $$$[0, 2^{pw} - 1]$$$.
In other words, we can for each $$$b_i$$$ choose: will we set several $$$0$$$-s and then $$$1$$$, or several $$$1$$$-s and then $$$0$$$. And that's only $$$2^{n - 1}$$$ states. Now for each such mask, let's iterate over the first bit-level $$$pw$$$ where we choose to make an opposite step (so on the next level we'll get the special situation). To calculate the answer for this $$$pw$$$ we can find for each $$$b_i$$$ the segment $$$[l, r]$$$ which will be uniquely determined by the mask, and calculate $$$dp[n][2][2]$$$, where $$$dp[pos][parity][flag]$$$ is the number of ways to choose $$$b_i$$$ from the whole segment $$$[l, r]$$$ on prefix of length $$$pos$$$ with XOR of $$$b_i(pw)$$$ equal to $$$parity$$$ and $$$flag$$$ is true if at least one $$$b_i(pw)$$$ was chosen in opposite to the mask way.
The answer for level $$$pw$$$ (total sum of all special cases on the next level) is equal to $$$dp[n][(a_1 \oplus \dots \oplus a_n)(pw)][1] \cdot 2^{-pw}$$$ (since we exclude length of the segment of one $$$[0, 2^{pw} - 1]$$$).
In total, the complexity of the solution is $$$O(2^n B \cdot n)$$$, but it needs a very careful implementation since we should set at least one $$$0$$$ before $$$1$$$ and handle situations where we have no actual choice since $$$l(pw) = r(pw)$$$.