正しい括弧列のうち、正しい括弧列 \(A,B\) を用いて \(A+B\) の形で書けないようなものを素晴らしい括弧列と呼ぶことにします（(), (()()) など）。

長さが同じ正しい括弧列の中で辞書順最大は () の繰り返しになります。

このため、 \(S\) が () の繰り返しである場合は \(T\) が \(S\) を部分列として含むことと同値であるため、簡単に計算できます。

以降 \(S\) は () の繰り返しでないものとします。

[1] \(T\) から辞書順最大の長さ \(K\) の正しい括弧列 \(T'\) を得るアルゴリズム

括弧からなる文字列 \(T\) から長さ \(K\) の部分列であって正しい括弧列のうち、辞書順最大の文字列 \(f(T)\) は以下の手順で得られます。

1. \(T\) はいくつかの正しい括弧列 \(t_1,t_2,\dots,t_n\) を用いて \(t_1 + \) ) \(+t_2 + \) ) \(+ \dots +\) ) \( + t_k + \) ( \(+t_{k+1}+\) ( \(+\dots +t_n\) という形で一意に表せる。この ))...)(...(( を取り除いて \(T\) を \(t_1+t_2+\dots +t_n\) に置き換える（この置き換えで \(|T|\) が \(K\) 未満になった場合、長さ \(K\) の部分列であって正しい括弧列は存在しない）。

2. つぎに () をくりかえして得られる長さ \(2k\) の正しい括弧列であって、以下の条件をすべてみたすようなものに対する \(k\) の 最大値を \(k_{max}\) とする。

   • \(T\) の部分列である
   • 先頭から貪欲に部分列に採用して残る \(T\) の接尾辞を \(T_{suf}\) としたとき、 \(T_{suf}\) の部分列であって長さ \(K-2k\) の正しい括弧列であるものが存在する

   すると \(f(T)\) の最初の \(2k_{max}\) 文字は () の繰り返しになる。

3. \(T\) の部分列として () を \(k_{max}\) 回繰り返して得られる文字列をとるとき、先頭から貪欲に部分列に採用して残る \(T\) の接尾辞を \(T'\) とする。 \(T'\) に対して 1 の置き換えを適応したあと、 \(T'\) の長さが \(K-2k_{max}\) になるまで以下を繰り返す。

   • \(T'\) は正しい括弧列 \(A,B\) を用いて ( \(+ A + \) ) \( + B\) と書ける。このとき \(T'\) を \(A+B\) で置き換える。

   以上の手順により得られた \(T'\) に対して、 \(f(T)\) は () を \(k_{max}\) 回繰り返して得られる文字列の末尾に \(T'\) を結合して得られる文字列になる。

まず \(1\) 番目の置き換えについて、))...)(...(( の最初の ) を部分列に用いる場合、それより前に部分列に用いられない ) が存在し、それと入れ替えたほうが辞書順は大きくなります。よって ))...)(...(( の最初の ) を使うことはなく、これを繰り返すといずれも部分列に用いられないことが分かります。

\(2\) 番目の手順の正当性は明らかです。

最後に \(3\) 番目の手順についてですが、これも先頭の ( の数を最小化していることから明らかに正しいです。途中で先頭の ( の数が \(1\) になるかについては、なると仮定すると \(2\) 番目の操作と矛盾している点に注意してください。

[2] \(S\) から \(T\) を復元する手順の数え上げ

\(S\) が () を \(a\) 回繰り返した後、 \(b\) 個の素晴らしい括弧列（ただし、最初の \(1\) 個は () ではない）を結合させたものであるとします。 \(a,b\) は \(O(K)\) 時間で簡単に計算できます。 \(b\neq 0\) であることに注意してください。

[1] を踏まえるとおおまかには以下の手順で \(T\) を復元できます。

1. \(b\) 個の素晴らしい括弧列を結合した文字列に (, ) をこの順で、括弧の対応関係を変更しないように挿入することを何度か行う。ただし、 ( はかならず先頭に挿入する。
2. 1で得られた正しい括弧列に対し、 ), ), ),…, (,(,( をこの順で、括弧の対応関係を変更しないように挿入して得られる文字列を \(X\) とする。
3. () を \(a\) 回繰り返して得られる文字列を部分列として含む文字列であって、先頭から貪欲に部分列として採用した場合末尾が採用されるようなもの（すなわち、末尾が削除されると部分列として含まなくなるようなもの）を適当に取り、 \(Y\) とする
4. \(T=Y+X\) として復元する

この手順での復元の結果、文字数が \(N\) になるものの数を形式的べき級数（fps）を用いて求めましょう。

まず \(3\) 番目の手順で作られる \(Y\) の、挿入文字数の fps は \(\frac{1}{(1-x)^{2a}}\) です。

つぎに \(1\) 番目の復元操作について考えます。 ) の挿入個所は \(b\) 通り考えられますが、これらの位置のうち \(1\) 個以上挿入する最も右の位置が左から \(i\) 番目であるようなものを考えます。まず \(1\) 番目の復元操作の結果得られる文字列の、挿入文字数についての fps は \(\frac{x^2}{(1-x^2)^i}\) です。 \(1\) 番目での挿入の後、文字列は \(b-i+1\) 個の素晴らしい括弧列に分解できるため、この後 \(2\) 番目の復元操作について挿入文字数についてのfpsは、\(\sum_{n=0}^{\infty} (n+1)[x^n]\frac{1}{(1-x)^{b-i+2}} = \frac{((b-i+1)x+1)}{(1-x)^{b-i+3}}\) です。

以上より \(1\) 番目の復元操作で挿入を \(1\) 回以上行う場合、復元過程全体での挿入文字数に関するfpsは

\[\displaystyle \frac{1}{(1-x)^{2a}}\sum_{i=1}^{b} \frac{x^2((b-i+1)x+1)}{(1-x^2)^i (1-x)^{b-i+3}} = \frac{bx^2}{(1-x)^{2a+b+3}}\]

になり、この \(x^{N-K}\) の係数は二項係数を用いて表すことができ、 \(O(N)\) 時間で求まります。

\(1\) 番目で \(1\) 回も挿入しない場合は簡単に計算できます。