企业官网建设流程全解析

括号序列（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的答案进行了一个哈希 巧妙的设计！ */#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e7+7,P=1e9+7;intst[N],top,match[N],f[N],g[N];// 不能全开ll，会MLEll ans[N];voidsolve(){string s;cin>>s;s=" "+s;for(inti=1;i<s.size();i++){if(s[i]=='(')st[++top]=i;elseif(top){intt=st[top--];match[i]=t,match[t]=i;}}for(inti=1;i<s.size();i++){if(s[i]==')'&&match[i])f[i]=f[match[i]-1]+1;}for(inti=s.size()-1;i>=1;i--){if(s[i]=='('&&match[i])g[i]=g[match[i]+1]+1;}top=0;for(inti=1;i<s.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 sum=0;for(inti=1;i<s.size();i++){sum+=i*ans[i]%P;}cout<<sum<<'\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;}