[1] Rephrasing the problem

The problem is equivalent to the following one:

There are $X+Y+Z+3$ points on a circumference, consecutively numbered $0$ to $X+Y+Z+2$.

There are three people standing at Points $0$, $X+1$, and $X+Y+2$. Now, let us perform the following operation $N$ times.

• Choose a person. Let $i$ be the index of the point he stands at, and send him to Point $(i+1) \bmod (X+Y+Z+3)$. Here, no two people may come to the same point.

Find the number of ways to perform $N$ operations, modulo $2$.

Below, let us solve this problem. We let \(M=X+Y+Z+3\), and call the people starting at Points \(0\), \(X+1\), and \(X+Y+2\) Person \(1\), \(2\), and \(3\), respectively.

---

[2] Looking it backward

Let us look at the process backward. That is, we try to find the number of ways where Persons \(1\), \(2\), and \(3\) end up at Points \(0\), \(X+1\), and \(X+Y+2\), respectively, but their initial positions do not matter as long as Persons \(1\), \(2\), and \(3\) stand in this order. This does not change the answer.

---

[3] Using dynamic programming

The problem above can be solved by dynamic programming where:

\(\mathrm{dp}[i][j][k]:=\) the number of ways to perform \(i\) operations after which (coordinate of Person \(2\)) \(-\) (coordinate of Person \(1\)) \(= j \bmod\ M\) and (coordinate of Person \(3\)) \(-\) (coordinate of Person \(2\)) \(= k \bmod\ M\) without no collisions so far, modulo \(2\),

with the following transition:

\(\begin{cases} \mathrm{dp}[i][j][k]=\mathrm{dp}[i-1][j-1][k]+\mathrm{dp}[i-1][j+1][k-1] + \mathrm{dp}[i-1][j][k+1](1 \le i \le N,1 \le j,k \le M-2,j+k \le M-1). \end{cases}\)

This should be initialized by \(\mathrm{dp}[0][j][k]=1\), and the answer is \(\mathrm{dp}[N][X+1][Y+1]\). Assume that all values at invalid indices are \(0\).

It takes \(\mathrm{O}(NM^2)\) time as it is, far beyond the limit.

---

[4] "Method of mirror images"

Below is a slice of \(\mathrm{dp}[i]\): (\(M=5\))

\(\mathrm{dp}[i][1][1]\ \mathrm{dp}[i][1][2]\ \mathrm{dp}[i][1][3]\)

\(\mathrm{dp}[i][2][1]\ \mathrm{dp}[i][2][2]\)

\(\mathrm{dp}[i][3][1]\)

Let us expand this \(\mathrm{dp}[i]\). Specifically, let us expand the range of \(j,k\) from \(1 \le j,k \le M-2,j+k \le M-1\) to \(0 \le j,k \le M-1\).

The entry where \(1 \le j,k \le M-2,j+k \le M-1\) does not hold is defined as follows:

\(\begin{cases} \mathrm{dp}[i][j][k]=0(j=0\ \mathrm{or}\ k=0\ \mathrm{or}\ j+k=0 \bmod\ M) \\ \mathrm{dp}[i][j][k]=\mathrm{dp}[i][M-k][M-j](\mathrm{else}). \end{cases}\)

Then, the transition can be done as follows:

\(\begin{cases} \mathrm{dp}[i][j][k]=\mathrm{dp}[i-1][j-1 \bmod M][k]+\mathrm{dp}[i-1][j+1 \bmod M][k-1 \bmod M] + \mathrm{dp}[i-1][j][k+1 \bmod M](1 \le i \le N,0 \le j,k \le M-1), \end{cases}\)

which can be proved by noting that \(\mathrm{dp}[i][j][k]=\mathrm{dp}[i][k][j]\) and \(\mathrm{dp}[i][j][k]=\mathrm{dp}[M-(j+k)][j]\).

That is, if we let \(f_i(x,y)=\sum_{j=0}^{M-1} \sum_{k=0}^{M-1} \mathrm{dp}[i][j][k] x^jy^k\), it holds that \(f_{i+1}(x,y)=f_i(x,y) \times \left(x + \frac{y}{x} + \frac{1}{y}\right) \bmod (x^M-1)(y^M-1)\).

Here, note that we may have \(f_0(x,y) = \left(\sum_{j=0}^{M-1} \sum_{k=0}^{M-1} x^jy^k \right) + \left(\sum_{j=0}^{M-1} x^j \right) + \left(\sum_{k=0}^{M-1} y^k \right) + \left(\sum_{j=0}^{M-1} x^jy^{M-j} \right)\) since we work modulo \(2\).

The answer is the coefficient of \(x^{X+1}y^{Y+1}\) in \(f_N(x,y)\). Let us consider each term in \(f_0(x,y)\). Below, we reduce everything modulo \((x^M-1)(y^M-1)\).

• $\left(\sum_{j=0}^{M-1} \sum_{k=0}^{M-1} x^jy^k \right)$ gets multiplied by all terms in $\left(x + \frac{y}{x} + \frac{1}{y}\right)^N$, so the coefficient of $x^{X+1}y^{Y+1}$ in $\left(\sum_{j=0}^{M-1} \sum_{k=0}^{M-1} x^jy^k \right) \times \left(x + \frac{y}{x} + \frac{1}{y}\right)^N$ is $1$.
• For $\left(\sum_{j=0}^{M-1} x^j \right)$, we may ignore $x$, so the coefficient of $x^{X+1}y^{Y+1}$ in $\left(\sum_{j=0}^{M-1} x^j \right) \times \left(x + \frac{y}{x} + \frac{1}{y}\right)^N$ equals the coefficient of $y^{Y+1}$ in $\left(1 + y + \frac{1}{y}\right)^N$.
• Similarly, the coefficient of $x^{X+1}y^{Y+1}$ in $\left(\sum_{k=0}^{M-1} y^k \right) \times \left(x + \frac{y}{x} + \frac{1}{y}\right)^N$ equals the coefficient of $x^{X+1}$ in $\left(x + \frac{1}{x} + 1\right)^N$.
• Similarly, the coefficient of $x^{X+1}y^{Y+1}$ in $\left(\sum_{j=0}^{M-1} x^jy^{M-j} \right) \times \left(x + \frac{y}{x} + \frac{1}{y}\right)^N$ equals the coefficient of $x^{X+Y+2}$ in $\left(x + 1 + \frac{1}{x}\right)^N$, since $x$ and $y$ do not have to be distinguished.

Therefore, solving the following problem three times will solve our problem.

Find the coefficient of $x^K$ in $\left(x + 1 + \frac{1}{x}\right)^N \bmod (x^M-1)$, modulo $2$.

Here, since \((x + y)^{2^a} = x^{2^a} + y^{2^a} \bmod 2\), we have \(\left(x + 1 + \frac{1}{x}\right)^N = \prod_{i=1}^{k} \left(x^{2^{A_i}} + 1 + x^{-2^{A_i}}\right)\) where \(N = 2^{A_1} + 2^{A_2} + 2^{A_3} + \dots + 2^{A_k}\). Note that \(k = \mathrm{O}(\log N)\).

---

[5] An $\mathrm{O}(M\log N)$ solution

The above problem can be solved by dynamic programming where \(\mathrm{dp}[i][j] = [x^j]\prod_{p=1}^{i} \left(x^{2^{A_p}} + 1 + x^{-2^{A_p}}\right)\), in \(\mathrm{O}(M \log N)\) time.

---

[6] An $\mathrm{O}\left(\frac{N\log N}{M}\right)$ solution

Let us multiply everything by \(x^N\) and consider \(\prod_{i=1}^{k} \left(1+x^{2^{A_i}} + x^{2^{A_i+1}}\right)\).

Here, instead of taking modulo \((x^M-1)\), let us take the sum of the coefficients of \(x^{K+iM}\) over all integers \(i\) such that \(x^{K+iM}\) and \(0 \le K +iM \le 2N\).

Then, the problem can be solved by solving the following one:

You are given positive integers $N$ and $X$. Find the number, modulo $2$, of triples of non-negative integers $A$, $B$, and $C$ such that $A+B+C=N$, $(A\ \mathrm{or}\ B\ \mathrm{or}\ C) = N$, and $B+2C=X$.

This can be solved by a digit DP that scans the bits of \(N\) in ascending order and maintains the carry, in \(\mathrm{O}(\log N)\) time.

We solve this subproblem \(\mathrm{O}\left(\frac{N}{M}\right)\) times, so this solution works in \(\mathrm{O}\left(\frac{N\log N}{M}\right)\) time.

---

[7] Summary

Therefore, one can solve the problem:

Find the coefficient of $x^K$ in $\left(x + 1 + \frac{1}{x}\right)^N \bmod (x^M-1)$, modulo $2$.

in \(\mathrm{O}(\sqrt N \log N)\) time by choosing one of the two solutions above that works faster, the original problem can also be solved in \(\mathrm{O}(\sqrt N \log N)\) time.