实际上我们需要计算的是有多少长为 nnn 的合法括号串 ttt 的字典序严格小于 sss。
枚举 s,ts,ts,t 的 lcp=i\operatorname{lcp}=ilcp=i。则有 si+1=),ti+1=(s_{i+1}=\texttt{)},t_{i+1}=\texttt{(}si+1=),ti+1=(。
ttt 再往后的部分只要求与前面构成合法括号串。这可以转化为格路径计数,组合数简单计算即可。
时间复杂度 O(n)O(n)O(n)。
注册一个 CZOJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 CZOJ 通用账户