まず、最終的な数列 \(B_1, B_2, \cdots, B_M\) を固定したときに、それが作成可能かを考える。

明らかに、以下の条件は必要である

• \(M = N \pmod 2\)
• \(B_i\) は全て異なる

それに加え、

• \(M + \Sigma_{i=0}^{M}{|B_i - B_{i+1}|} \le N\)

が必要である。ただし、\(B_0 = B_{M + 1} = 0\) とする。これは、操作によって左辺が増えないことから示せる。

そして、実はこれらが必要十分条件である。これらを満たすなら、\(B\) に対して「\(2\) 個 \(0\) を挿入し、その間の値を全て \(-1\)」という操作を繰り返して、長さ \(N\) 以下のすべての要素が \(0\) の数列が出来る。この操作を逆向きに見れば \(A\) から \(B\) を構築する操作列が得られる。

あとは、これらの条件を満たす \(B\) を数え上げればよい。\(B_i\) は全て異なる、という制約を扱うために、値を小さいほうから順に \(B\) に挿入していくDPを考える。つまり、空配列から始め、 \(0\) を高々 \(1\) 個挿入 → \(1\) を高々 \(1\) 個挿入 → … という操作を繰り返して \(B\) を構築することを考える。

実際に、\( \Sigma_{i=0}^{M}{|B_i - B_{i+1}|}\) もこの構築法と相性が良い。なぜならこの値は「全ての値 \(x\) についての、 \(x\) 以下の要素と \(x + 1\) 以上の要素が隣り合う箇所の個数の総和」と等しいからである。

具体的に保持すべき情報は 「\(|B| + 1\) 個の要素の間(または端)のうち、将来そこに要素を \(1\) 個以上挿入するものの個数」である。なぜならこの個数が先述の「\(x\) 以下の要素と \(x + 1\) 以上の要素が隣り合う箇所の個数」に対応するからである。これを保持しておけば、\(M + \Sigma_{i=0}^{M}{|B_i - B_{i+1}|}\) がincrementalに計算可能である (\(M\) については要素を追加するたびに \(1\) 増やしていけばよい)。

これで、以下の情報を保持した \(O(N^2)\) 時間の DP が可能である。特に、実は「次に新しく追加を検討する値」は状態として持つ必要はない。

• \(|B| + 1\) 個の要素の間(または端)のうち、将来そこに要素を \(1\) 個以上挿入するものの個数
• 現在の \(M + \Sigma_{i=0}^{M}{|B_i - B_{i+1}|}\)

最後に、前者の値は高々 \(1\) ずつしか増えないこと、そして後者の値はそれまでの前者の値の総和以上であることを合わせると、実は前者の値が高々 \(O(\sqrt {N})\) であることがわかる。よってこのDPは \(O(N \sqrt{N})\) 時間で動作する。