Consider a Dynamic Programming (DP) where we define “\(\mathrm{dp}_X[i][j]:=\) the number of ways to choose \(j\) elements modulo \(2\) so that the sum of elements is \(i\).” Computing this DP for all \(X=(A_1),(A_1,A_2),(A_1,A_2,A_3),\dots\) costs \(\mathrm{O}(NM)\) time, which does not finish in the time limit.

Let \(\mathrm{dp'}_X[i]=\sum_{j=0}^{\infty} \mathrm{dp}_X[j][i] x^j\). That is, \(\mathrm{dp'}_X[i]\) is a polynomial that has the sum of chosen elements as the indices of \(x\).

Here, suppose we have already obtained \(\mathrm{dp'}_X\) and \(\mathrm{dp'}_Y\) for two sequences \(X\) and \(Y\). Consider finding \(\mathrm{dp'}_Z\) for a sequence \(Z\) that is a concatenation of \(X\) and \(Y\). This can be computed by the following transitions:

\(\begin{cases} \mathrm{dp'}_Z[0]=\mathrm{dp'}_X[0] \times \mathrm{dp'}_Y[0] + \mathrm{dp'}_X[1] \times \mathrm{dp'}_Y[1] \\ \mathrm{dp'}_Z[0]=\mathrm{dp'}_X[1] \times \mathrm{dp'}_Y[0] + \mathrm{dp'}_X[0] \times \mathrm{dp'}_Y[1] \end{cases}\)

Here, \(\times\) denotes the multiplication of polynomials. The transition can be computed fast by using convolution for multiplications.

Let’s get back to the original problem. Initially, we have \(\mathrm{dp'}_{(A_1)},\mathrm{dp'}_{(A_2)},\dots,\mathrm{dp'}_{(A_N)}\). Let \(f=\) be these sequence. We merge them as follows:

• Repeat the following while the length of $f$ is $2$ or more.
• Choose two initial elements of $f$.
• Merge those two by the equations above. Append the resulting $\mathrm{dp'}$ to the tail of $f$.

We analyze the complexity. For each initial \(\mathrm{dp'}_{(A_i)}\), the \(\mathrm{dp'}\) that it belongs are called at most \(\mathrm{O}(\log N)\) time, so the complexity is \(\mathrm{O}(M \log M \log N)\).

Therefore, the problem can be solved in a total of \(\mathrm{O}(M \log M \log N)\) time, which is fast enough.