Easy Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 766    Accepted Submission(s): 208

 

Problem Description

soda has a string containing only two characters -- '(' and ')'. For every character in the string, soda wants to know the number of valid substrings which contain that character.

Note:

An empty string is valid. If S is valid, (S) is valid. If U,V are valid, UV is valid.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

A string s consisting of '(' or ')' $(1 \leq |s| \leq 10^6)$.

Output

For each test case, output an integer $m=\sum_{i=1}^{|s|}(i⋅ansi mod 1000000007)$, where ansi is the number of valid substrings which contain i-th character.

Sample Input

2

()()

((()))

Sample Output

20

42

Hint

For the second case, $ans = \{1, 2, 3, 3, 2, 1\}$, then $m=1 \cdot 1 + 2 \cdot 2 + 3 \cdot 3 + 4 \cdot 3 + 5 \cdot 2 + 6 \cdot 1 = 42$

Author

zimpha@zju

 

Source

 1005

 

解题：栈

 

貌似还是有点不明白，代码先放着

 

1 #include 
       
         2 using namespace std; 3 typedef long long LL; 4 const LL mod = 1000000007; 5 const int maxn = 2000010; 6 char str[maxn]; 7 int stk[maxn],match[maxn],pre[maxn],a[maxn],b[maxn],top; 8 LL ans[maxn]; 9 int main() {10     int kase,n;11     scanf("%d",&kase);12     while(kase--) {13         scanf("%s",str + 1);14         top = 0;15         n = strlen(str + 1);16         for(int i = 1; i <= n; ++i) {17             match[i] = pre[i] = 0;18             if(str[i] == '(') stk[++top] = i;19             else if(top) {20                 match[stk[top]] = i;21                 match[i] = stk[top];22                 if(top > 1) pre[match[i]] = stk[top-1];23                 stk[top--] = 0;24             }25         }26         ans[0] = a[0] = b[n+1] = 0;27         for(int i = 1; i <= n; i++)28             a[i] = (str[i] == ')' && match[i])?(a[match[i] - 1] + 1):0;29         for(int i = n; i >= 1; i--)30             b[i] = (str[i] == '(' && match[i])?(b[i] = b[match[i] + 1] + 1):0;31         for(int i = 1; i <= n; i++)32             ans[i] = (str[i] == '(')?(ans[pre[i]] + ((LL)b[i]*a[match[i]] % mod) % mod):ans[match[i]];33         LL ret = 0;34         for(int i = 1; i <= n; ++i)35             ret += ans[i]*i%mod;36         printf("%I64d\n",ret);37     }38     return 0;39 }