本文主要是介绍已经没有什么好害怕的了，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
小Y 最近开始学习算法姿势，但是因为小R 非常BB，给了她很多B6 题，所以她觉得自己已经没有什么前途了。于是小R 给了她一些稍微简单的题，让她觉得已经没有什么好害怕的了，其中一道是这样的：
给定一个长度为n 只包含左括号和右括号的序列，现在小R 想要知道经过每一个位置的合法子串有多少个。
空串是一个合法的串，如果A 和B 都是合法的串，那么(A) 和AB 都是合法的串。
Input
第一行输入一个正整数T 表示数据组数。接下来T 行每行一个字符串。
Output
对于每组数据，输出一个整数表示答案，令ansi 为经过第i 个位置的子串个数，那么你需要输出(注意是先求余再求和)
Sample Input
1
()()
Sample Output
20
样例解释：
ans 数组为{2,2,2,2}，所以输出20。
Data Constraint
对于10% 的数据，n<=100
对于30% 的数据，n <= 1000
对于60% 的数据，n <= 5 <= 10^4
对于100% 的数据，n <= 10^6，1 <= T<= 10
.
.
.
.
.
.
分析
栈+差分约束
用栈处理对应的括号
把整个字符串拆成几段（跳过没用的括号），然后计算即可
对于每一段序列，我们从大到小处理，即从整体到局部
再用差分约束的思想求出每个点所被经过的合法的括号序列的个数
.
.
.
.
.
程序：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;int n,a[1000010],l[1000010],r[1000010],f[1000010],next[1000010],last[1000010];
char zf[1000010];
long long ans,t[1000010];void work()
{memset(l,0,sizeof(l));memset(r,0,sizeof(r));memset(t,0,sizeof(t));for (int i=n+1;i>=1;i--) {r[i]++;r[last[i]]+=r[i];}for (int i=1;i<=n;i++) {l[i]--;l[next[i]]+=l[i];}for (int i=1;i<=n;i++) t[i]=r[i]+l[i];for (int i=1;i<=n;i++) t[i]+=t[i-1];long long ans=0;for (int i=1;i<=n;i++) ans=(long long)ans+(long long)i*t[i]%1000000007;printf("%lld\n",ans);
}int main()
{int t;scanf("%d",&t);while (t--) {scanf("%s",zf+1);n=strlen(zf+1);memset(f,0,sizeof(f));memset(last,0,sizeof(last));memset(next,0,sizeof(next));int head=0;for (int i=1;i<=n;i++) if (zf[i]=='(') f[++head]=i; else if (head!=0){next[f[head]]=i+1;last[i+1]=f[head--];}work();}
}
这篇关于已经没有什么好害怕的了的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
