[Round#404 Div.2] D. Anton and School - 2

http://codeforces.com/contest/785/problem/D

괄호문자열이 주어지면 문자열에 있는 괄호들을 임의로 선택하여 만들 수 있는 RSBS(regular simple bracket sequences)의 개수를 찾아 그 개수를 1e9+7로 나눈 나머지를 출력하는 문제이다.

RSBS란

• It is not empty (that is n ≠ 0).
• The length of the sequence is even.
• First  charactes of the sequence are equal to "(".
• Last  charactes of the sequence are equal to ")".

인데 간단히 말해 앞쪽은 n/2개의 '(' 뒤쪽은 n/2개의 ')'로 이루어진 괄호를 말한다. 즉 (())나 ((()))같은 것들이다.

Examples

input

)(()()

output

6

input

()()()

output

7

input

)))

output

0

1번케이스는 (2,4) (2,6) (3,4) (3,6) (5,6) 으로 ()를 만들 수 있고, (2,3,4,6)으로 (())를 만들 수 있다.

일단 먼저 앞에서부터 쭉 훑으면서 i번째 지점에 왔을때 '('가 몇개인지, 뒤에서 부터 훑으면서 ')'가 몇개인지를 전처리해놓을 수 있다. O(N)

다시 앞에서부터 훑으면서 i번째 지점에서 '('가 발견되었다면, i번째에 있는 '('를 반드시 사용하여 만들 수 있는 RSBS의 조합의 개수를 구해서  더해주면 된다.

여기까지는 쉽게 생각할 수 있으나.. 조합의 개수를 구하는게 관건인 문제이다.

생각해보면 1~i지점까지 존재하는 '('의 개수를 A[i]라 하고, (i)~N지점사이에 존재하는 ')'의 개수를 B[i]라 하면

i지점에서 만들 수 있는 괄호의 조합수는 아래와 같고, 조합의 성질을 이용해 우변처럼 바꿀 수 있다.

사실상 이 조합의 product sum을 각 지점별로 다 구한다면 당연히 TLE가 떨어지고, 이 식을 간단하게 바꿀 방법을 고민해봐야한다.

만약 그 방법을 찾았다면,  '('이 나오는 지점에서 위 식의 결과값을 구해 이를 모두 더해주면 된다.

[HINT]

N은 20만이기때문에 corner에선 A[i]와 B[i]가 10만에 가까운 값이 나올 수 있기 때문에, 조합을 구할 때 naive한 방법이나 pascal's triangle을 이용한 dp로서의 접근은 불가능하다. 따라서 fermat's little thm이나 그밖의 combination을 빠르게 구할 수 있는 방법을 이용하여 조합을 구해내면 된다.

당연한 것이지만 조합을 구할때 factorial은 메모이제이션하는 기본적인 센스는 갖추도록 하자.

(메모이제이션 안했더니 TLE나서 한참을 헤멤;;)