5357：Easy Sequence

题目描述

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.

输入解释

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)$.

输出解释

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.

输入样例

2
()()
((()))

输出样例

20
42

提示


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$

来自杭电HDUOJ的附加信息

Author	zimpha@zju
Recommend	wange2014

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2015 Multi-University Training Contest 6

源链接： HDU-5357

最后修改于 2020-10-25T23:21:59+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	131072/131072K(Java/Others)