\(\Theta(S)\) 解法

問題文の条件をみたす \(X\) の総数は、\(T = \{0, 1, \dots, S \} \setminus \{A_1, \dots, A_N\}\) に属する整数を以下の条件を満たすように (好きな個数) 選ぶ方法の総数に等しいです。

• \(0, S\) は必ず選ぶ。
• 選んだ整数を小さい順に並べたとき、隣接する整数の偶奇が異なる。

「\(S\) は必ず選ぶ」という条件は一旦無視することにして、次のような動的計画法を考えます。

\(\text{dp}_{i, j} := \) \(T\) に属する \(i\) 以下の整数を選ぶ方法であって、上記の条件を満たし、かつ現在選んでいる最大の整数を \(2\) で割った余りが \(j\) であるようなものの総数。

\(i \rightarrow i+1\) の遷移は次のようになります。

• \(j = 0, 1\) について \(\text{dp}_{i + 1, j}\) に \(\text{dp}_{i, j}\) を加える。これは \(i+1\) を選ばないような方法に対応する。
• \(i+1 \notin T\) ならば、\(i + 1\) を \(2\) で割った余りを \(j\) として、\(\text{dp}_{i + 1, j}\) に \(\text{dp}_{i, 1 - j}\) を加える。これは \(i+1\) を選ぶような方法に対応する。

最後に「\(S\) は必ず選ぶ」という条件を加えると、\(S\) の直前に選んだ整数と \(S\) は偶奇が一致しなければならないので、\(S\) を \(2\) で割った余りを \(p\) として、\(\text{dp}_{S-1, p}\) が答えとなります。

以上から、この問題を \(\Theta(S)\) で解くことができました。

\(O(N \log S)\) 解法

上記の解法は同じような遷移を何度も繰り返しています。これを高速化する方法を説明します。

まず、\(\text{dp}\) を以下のように再定義します。

\(\text{dp}_{i, j} := \) \(T\) に属する \(i\) 以下の整数を選ぶ方法であって、上記の条件を満たし、かつ現在選んでいる最大の整数と \(i + j\) の偶奇が等しいようなものの総数。

すると遷移は次のように変わります。

• \(\text{dp}_{i + 1, 0}\) に \(\text{dp}_{i, 1}\) を加え、\(\text{dp}_{i + 1, 1}\) に \(\text{dp}_{i, 0}\) を加える。
• \(i + 1 \notin T\) ならば、\(\text{dp}_{i + 1, 0}\) に \(\text{dp}_{i, 0}\) を加える。

\(i + 1 \in T\) となるような場合の遷移は愚直に行うことにして、\(i + 1 \notin T\) の場合を考えます。\(\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}\) が成り立つので、行列累乗を用いると、常に \(i + 1\notin T\) となるような \(i\) の区間における遷移はまとめて \(O(\log S)\) で行うことができます。よって、\(i = 0\) から \(i = S-1\) までの遷移は、

• 高々 \(N+1\) 回の \(O (\log S)\) の遷移
• \(N\) 回の定数時間の遷移

で行うことができます。以上から、この問題を \(O(N \log S)\) で解くことができました。

実装例 (C++)