問題文中の条件より、 \(T\) は正規括弧列です。

まず、操作を逆順に考えることで \(T\) から () を取り除く問題だと解釈します。

次に、括弧列を根付き木のオイラーツアーと解釈して \(N\) 辺(つまり \(N+1\) 頂点)の根付き木に変換することで、木の問題に置き換えます。

元の問題は、この変換した木から葉を取り除いていき最終的に \(0\) 頂点にする操作の方法を数え上げる問題と同値です。よって、以下のように変形できます。

\(N+1\) 頂点の根付き木が与えられる。以下の条件を満たす順列 \(P\) の個数を数え上げよ。

• \(i\) が \(j\) の親であるようなすべての整数対 \((i,j)\) について、 \(P_i > P_j\)

この値は葉から部分木内の順序関係のみを考えた場合の数を持ちながら根に向かってマージしていくことで \(O(N)\) で求めることができます。

以上より、この問題を時間計算量 \(O(N)\) で解くことができました。

実装例 (C++)