順列 \(P\) において、\(i\) より大きい要素を区切りとみなしたときの、\(1,2,\ldots,i\) からなる極大な連続部分列を ブロック と呼びます。

\(1,2,\ldots,i\) を順に追加していくことを考えます。\(i\) を追加する直前のブロック列から、追加後のブロック列を作る方法は次の \(3\) 通りです。

• \(i\) を単独のブロックとして挿入する。
• いずれかのブロックの左端または右端に追加する。
• 隣接する \(2\) ブロックを \(i\) で連結する。

各順列について、各 \(i\) でのブロック列は一意に定まるため、この操作によって順列を重複なく数えられます。

\(f_{i,j}\) を、\(1,2,\ldots,i\) を追加した時点でブロック数が \(j\) であり、\(S_1,S_2,\ldots,S_i\) の条件を満たす場合の数とします。

\(1\) は必ず単独で連続部分列をなすため、\(S_1=\) x なら答えは \(0\) です。

以下、\(S_1=\) o とし、\(f_{1,1}=1, f_{1,j}=0 \quad (j\geq 2)\) を初期値とします。

\(i\) を追加した直後のブロック数を \(j\) とします。

• \(i\) を単独のブロックとして挿入する場合、元の \(j-1\) ブロックの間または両端の \(j\) 箇所から挿入位置を選ぶので、 \(j f_{i-1,j-1}\) 通りです。

• 既存のブロックの端に追加する場合、\(j\) 個のブロックの左右どちらかの端を選ぶので、 \(2j f_{i-1,j}\) 通りです。

• 隣接する \(2\) ブロックを連結する場合、元の \(j+1\) ブロックの間から選ぶので、 \(j f_{i-1,j+1}\) 通りです。

したがって、 \(S_i=\) o のとき、ブロック数は \(1\) でなければならないため、

\[ f_{i,1}=2f_{i-1,1}+f_{i-1,2} \]

\[ f_{i,j}=0\qquad (j\geq 2) \]

となり、\(S_i=\) x のとき、ブロック数は \(2\) 以上である必要があるため、

\[ f_{i,1}=0 \]

\[ f_{i,j}=j f_{i-1,j-1} +2j f_{i-1,j} +j f_{i-1,j+1}\qquad (j\geq 2) \]

となります。

最終的には \(1,2,\ldots,N\) のすべてが一つの順列をなす、すなわちブロック数が \(1\) になる必要があるため、答えは \(f_{N,1}\) です。

状態数は \(O(N^2)\) で、各遷移は \(O(1)\) なので、計算量は \(O(N^2)\) です。