|
||||||||||
Easy SequenceTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 1278 Accepted Submission(s): 342 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 \le |s| \le 10^6)$. Output For each test case, output an integer $m =\displaystyle \sum_{i = 1}^{|s|} (i\cdot ans_i \text{ mod } 1000000007)$, where $ans_i$ is the number of valid substrings which contain $i$-th character. Sample Input
Sample Output
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 | ||||||||||
|