\(\Theta(S)\) Solution

The total number of \(X\) satisfying the conditions in the Problem Statement is equal to the total number of ways to choose (arbitrary number of) integers from \(T = \{0, 1, \dots, S \} \setminus \{A_1, \dots, A_N\}\) so that:

• \(0\) and \(S\) are always chosen; and
• when the chosen integers are arranged in ascending order, adjacent integers have different parities.

Let us first ignore the condition “\(S\) is always chosen” and consider the following Dynamic Programming (DP):

\(\text{dp}_{i, j} := \) the number of ways to choose integers from \(T\) that are less than or equal to \(i\), such that the conditions above are satisfied and the remainder when the maximum chosen integer is divided by \(2\) is \(j\).

The transition \(i \rightarrow i+1\) will be as follows:

• For \(j = 0, 1\), add \(\text{dp}_{i, j}\) to \(\text{dp}_{i + 1, j}\), which corresponds to not choosing \(i+1\).
• If \(i+1 \notin T\), then add \(\text{dp}_{i, 1 - j}\) to \(\text{dp}_{i + 1, j}\), where \(j\) is the remainder of \((i+1)\) divided by \(2\), which corresponds to choosing \(i+1\).

Finally, if we consider the condition “\(S\) is always chosen,” \(S\) should have the same parity to the final integer chosen, so the answer is \(\text{dp}_{S-1, p}\) where \(p\) is the remainder of \(S\) divided by \(2\).

Therefore, the problem has been solved in a total of \(\Theta(S)\) time.

\(O(N \log S)\) Solution

The solution above repeats almost the same transition over and over again. We will explain how to optimize it.

First, let us re-define \(\text{dp}\) as follows:

\(\text{dp}_{i, j} := \) the number of ways to choose integers from \(T\) that are less than or equal to \(i\), such that the conditions above are satisfied and the parity of the maximum integer chosen and \((i+j)\) are the same.

Then the transition will be as follows.

• Add \(\text{dp}_{i, 1}\) to \(\text{dp}_{i + 1, 0}\) and \(\text{dp}_{i, 0}\) to \(\text{dp}_{i + 1, 1}\).
• If \(i + 1 \notin T\), then add \(\text{dp}_{i, 0}\) to \(\text{dp}_{i + 1, 0}\).

While we process the transition for \(i + 1 \in T\) naively, we will consider the transitions for \(i + 1 \notin T\). Since \(\begin{pmatrix} \text{dp}_{i+1, 0} & \text{dp}_{i + 1, 1} \\ \end{pmatrix} = \begin{pmatrix} \text{dp}_{i, 0} & \text{dp}_{i, 1} \\ \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}\), we can utilize fast matrix exponentiation to process the transitions for the segment for \(i\) where \(i + 1\notin T\) always holds in an \(O(\log S)\) time. Thus, the transitions from \(i = 0\) to \(i = S-1\) is processed by:

• \(N+1\) transitions of \(O (\log S)\) time each, and
• \(N\) transitions of a constant time each.

Therefore, the problem has been solved in a total of \(O(N \log S)\) time.

Sample code (C++)