实际上我们需要计算的是有多少长为 $n$ 的合法括号串 $t$ 的字典序严格小于 $s$。

枚举 $s,t$ 的 $\operatorname{lcp}=i$。则有 $s_{i+1}=\texttt{)},t_{i+1}=\texttt{(}$。

$t$ 再往后的部分只要求与前面构成合法括号串。这可以转化为格路径计数，组合数简单计算即可。

时间复杂度 $O(n)$。