1 条题解

  • 0
    @ 2024-6-1 11:26:01

    实际上我们需要计算的是有多少长为 nn 的合法括号串 tt 的字典序严格小于 ss

    枚举 s,ts,tlcp=i\operatorname{lcp}=i。则有 si+1=),ti+1=(s_{i+1}=\texttt{)},t_{i+1}=\texttt{(}

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

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

    信息

    ID
    910
    时间
    2000ms
    内存
    512MiB
    难度
    10
    标签
    (无)
    递交数
    7
    已通过
    3
    上传者