• \(B=1,2,\dots ,M\) について, 異なる位置にある \(2\) つの \(B\) の間（両端を含む）には \(X_B\) が存在する.

という条件を単に条件と呼ぶことにします.

\(A\) の要素を先頭から決めていくことを考えます. \(A_i\) を決める際には, \((A_1,A_2,\dots ,A_i)\) が条件を満たすような \(A_i\) を選ぶことにします.

そこで, 次のような動的計画法を考えましょう.

• \(A\) の先頭から \(c(=0,1,\dots ,N)\) 項を決めて, \(A_{c+1}\) としてあり得るものの集合が \(S(\subset\lbrace 1,2,\dots ,M\rbrace)\) であるような方法の個数を \(\mathrm{dp}[c][S]\) とする.

まず, \(A_1\) としては \(1,2,\dots ,M\) のすべてがあり得ます. したがって \(\mathrm{dp}[0][\lbrace 1,2,\dots ,M\rbrace] = 1\) です.

次に \(c,S\) が固定されているときに \(A_{c+1}\) を \(a\in S\) に決めるとどうなるかを考えます.

まず, \(a\) と \(a\) の間に \(X_a\) が存在するという条件から, \(S\) から \(a\) を除きます. このことは, \(X_a\) を追加するまで \(a\) を追加してはいけない, と解釈することができます. 次に, \(X_b=a\) なる \(b\) をすべて \(S\) に加えます. このことは, \(X_b\) が追加されたので \(b\) を追加してもよくなった, と解釈することができます. こうして得られた新しい \(S\) を \(S(a)\) と書くことにすると, 動的計画法の遷移は次のように書くことができます.

• \(\mathrm{dp}[c+1][S(a)]\xleftarrow{+} \mathrm{dp}[c][a]\quad (a\in S)\)

これは一種の bitDP です. 時間計算量は \(\mathrm{O}(NM2^M)\) で, 制約下で十分高速に動作します.