\(S_1=S_N=\text{o}\) を仮定します。

集合 \(T\subset\{1,2,\dots,N\}\) に対し、 \(f(T)\) を以下のように定めます。

• \(P\) であって、 \(k\in T\) に対し \((1,2,\dots,k)\) の順列が \(P\) の連続部分列になるようなものの数。

このとき、 \(S_k=\text{o}\) なる \(k\) の集合を \(O\) とすると、包除原理より答えは以下の式で表されます。

\[\sum_{O\subset P\subset\{1,2,\dots,N\}}f(P)(-1)^{|P|-|O|}\]

これは動的計画法により求めることができます。まず \(dp[i]\) を以下のように定めます。

• \(N=i\) としたとき、集合 \(T(O\cap\{1,2,\dots,i\}\subset T\subset\{1,2,\dots,i\},i\in T)\) に対する \(f(T)(-1)^{|T|}\) の総和。

これを求める方法を考えます。まず明らかに \(dp[1]=-1\) です。また \(i\ge 2\) に対し、 \(dp[i]\) を求める過程における \(T\) の \(2\) 番目に大きい要素を \(j\) とすると、 \(dp[j]\) から \(dp[i]\) への遷移は、 \((1,2,\dots,j)\) の順列を \(1\) つの塊と見れば、 \(dp[i]+\!=-dp[j](i-j+1)!\) とわかります。ただし \(O\) の要素をまたぐことはできないので注意してください。

このとき最終的な答は \(dp[N](-1)^{|O|}\) となります。よって \(O(N^2)\) で求めることができました。