文章目录括号序列bracket【题目描述】【题解】括号序列bracket【题目描述】给定一个由左右括号构成的字符串 s 对于每一个位置 i 输出有多少个子串满足这个子串是一个合法的括号序列并且这个位置 i 在子串中。其中合法的括号序列定义如下• 空串是合法的。• 如果 S 是合法的那么 ( S ) 也是合法的。• 如果 U, V 是合法的那么 UV 也是合法的。【输入格式】从文件 bracket.in 中读入数据。一行一个由左右括号构成的字符串 S 。【输出格式】输出到文件 bracket.out 中。由于答案可能很大输出 ∑(i · ansi mod (10^9 7)) 即可其中 ansi 表示第 i 个位置的答案。【样例 1 输入】(()())【样例 1 输出】49【样例 1 解释】这里的 ans 分别为 ( 1, 3, 3, 3, 3, 1 )。【样例 2】见选手目录下的 bracket/bracket2.in 与 bracket/bracket2.ans。【子任务】共十组数据。• 对于 30% 的数据保证 ( |S| ≤ 5000 )。• 对于 70% 的数据保证 ( |S| ≤ 10^6 )。• 对于 100% 的数据保证 ( |S| ≤ 10^7 )。【题解】/* 遇到子串的括号匹配问题有一个套路的dp是设f[i]表示以i为结尾的合法括号序列个数转移可以找上一个匹配的括号并从前一个转移 f[i]f[st[top]-1]1当i为右括号 对于本题由于位置i可能包含其位于其左右的更大的序列所以不妨升级一下设f[i]表示1~i以i结尾的合法括号串个数g[i]表示i~n以i为结尾的合法括号串个数假设s[i](g[i]) f[i]f[match[i]-1]1, g[i]g[match[i]1]1 那么对于位置i假设s[i](如果它的匹配位置为match[i]则包含它的括号序列个数就是ans[i]g[i]*f[match[i]]可以理解为分别找i之前可用的左端点个数和match[i]之后可用的右端点个数根据乘法原理左右相乘即为方案数 发现一对配对的左右括号的ans一定相等据此统计答案即可 但是发现一个bug根据dp的逻辑每次从栈顶转移匹配的括号意味着我们统计的个数都是层数与i同级的括号串但比i的级别还大的外层括号串被我们忽略了 例如{()()()()()} 两个大括号组成的合法串被忽略了。我们可以考虑在大括号匹配闭合时对其内部的所有ans[i]都差分去1。 更巧妙的实现是对于每个ans[i]多转移一步ans[i]ans[st[top]]相当于加上栈中上一级未匹配括号的贡献这样不漏的原因是ans[st[top]]中一定也包含了上一级以及更上级的方案数之和是包含在里面的 彩蛋答案“∑(i · ansi mod (10^9 7))”只让内层取模并没有取模外层是因为如果外层取模根据同余模定理会有纯组合数学的计算方法出题人为了卡掉这种方法才这样设计输出 其实当然也可以对每个位置输出答案但10^7个输出太多了这也相当于是对整个S的答案进行了一个哈希 巧妙的设计 */#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN1e77,P1e97;intst[N],top,match[N],f[N],g[N];// 不能全开ll会MLEll ans[N];voidsolve(){string s;cins;s s;for(inti1;is.size();i){if(s[i]()st[top]i;elseif(top){inttst[top--];match[i]t,match[t]i;}}for(inti1;is.size();i){if(s[i])match[i])f[i]f[match[i]-1]1;}for(intis.size()-1;i1;i--){if(s[i](match[i])g[i]g[match[i]1]1;}top0;for(inti1;is.size();i){if(s[i](){ans[i]1ll*g[i]*f[match[i]]%P;if(top)ans[i](ans[i]ans[st[top]])%P;st[top]i;}elseif(top){top--;}ans[match[i]]ans[i];// 对于每个右括号答案等于与之匹配的左括号}ll sum0;for(inti1;is.size();i){sumi*ans[i]%P;}coutsum\n;}signedmain(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);// freopen(bracket.in, r, stdin);// freopen(bracket.out, w, stdout);solve();return0;}
原理与应用实践)
