25021번 - 알록달록한 괄호열 서브태스크언어 제한함수 구현

문제

괄호열이란 두 종류의 문자 (또는 )로 이루어진 문자열이다.

좋은 괄호열이란 다음과 같은 규칙을 통해 만들어질 수 있는 괄호열이다.

• 빈 문자열은 좋은 괄호열이다.
• S가 좋은 괄호열이면 (S)도 좋은 괄호열이다. 이 때, S의 양 끝에 붙인 두 괄호는 짝지어졌다고 한다.
• S와 T가 좋은 괄호열이면 ST도 좋은 괄호열이다.

색칠된 괄호열이란 각 괄호가 특정한 색으로 칠해진 괄호열이다.

알록달록한 괄호열이란 다음의 조건을 모두 만족하는 색칠된 괄호열이다.

• 색을 무시하고 괄호의 형태만 봤을 때 좋은 괄호열이다.
• 모든 인접한 두 괄호의 색이 다르다.
• 모든 짝지어진 두 괄호의 색이 다르다.

문자열 $S$에서 하나 이상의 문자를 뽑아 순서대로 나열한 것이 $T$일 때, $S$에서 $T$를 뽑아낼 수 있다고 한다.

색칠된 괄호열이 주어질 때, 이 괄호열에서 뽑아낼 수 있는 알록달록한 괄호열은 몇 가지일까?

괄호의 형태가 같은 색칠된 괄호열이 여럿 있을 수 있지만 색이 다른 괄호가 하나라도 있으면 다른 경우로 봐야 하며, 문자를 뽑는 방식이 여럿이더라도 결과가 같으면 한 가지 경우로 봐야 한다.

구현

여러분은 아래 함수를 구현해야 한다.

int count(vector<int> P)

• 이 함수는 단 한 번만 호출된다.
• $P$: 색칠된 괄호열을 나타내며, $P[i]$는 $i$번째 괄호의 정보를 나타낸다. $P[i] < 0$이면 (를, $P[i] > 0$ 이면 )를 나타내며, $|P[i]|$의 값에 따라 색을 구별한다.
• 이 함수는 주어진 색칠된 괄호열에서 뽑아낼 수 있는 알록달록한 괄호열의 개수를 1ドル,000円,000円,007円$로 나눈 나머지를 반환해야 한다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

에제 1

c색으로 칠해진 괄호 p를 $\underset{c}{p}$로 나타낸다.

색칠된 괄호열 $\underset{1}{(} \underset{2}{)} \underset{3}{(} \underset{3}{)} \underset{1}{(} \underset{2}{)} $이 주어지면, 그레이더는 다음과 같이 함수를 호출한다.

count({ -1, 2, -3, 3, -1, 2 })

여기서 뽑아낼 수 있는 알록달록한 괄호열은 $\underset{1}{(} \underset{2}{)} ,ドル $\underset{1}{(} \underset{3}{)} ,ドル $\underset{3}{(} \underset{2}{)} ,ドル $\underset{1}{(} \underset{2}{)} \underset{1}{(} \underset{2}{)} ,ドル $\underset{1}{(} \underset{2}{)} \underset{3}{(} \underset{2}{)} ,ドル $\underset{1}{(} \underset{3}{)} \underset{1}{(} \underset{2}{)} $의 6ドル$가지이다. 그러므로, 호출된 count 함수는 6ドル$을 반환해야 한다.

특정 문자열을 뽑아내는 방법은 여럿이 있을 수 있으며, 이 예제에서 $\underset{1}{(} \underset{2}{)} $를 뽑는 방법은 3가지가 있다.

예제 2

색칠된 괄호열 $\underset{1}{(} \underset{6}{)} \underset{3}{(} \underset{6}{(} \underset{1}{)} \underset{1}{(} \underset{3}{)} \underset{6}{)} $이 주어지면, 그레이더는 다음과 같이 함수를 호출한다.

count({ -1, 6, -3, -6, 1, -1, 3, 6 })

여기서 뽑아낼 수 있는 알록달록한 괄호열은 $\underset{1}{(} \underset{3}{)} ,ドル $\underset{1}{(} \underset{6}{)} ,ドル $\underset{3}{(} \underset{1}{)} ,ドル $\underset{3}{(} \underset{6}{)} ,ドル $\underset{6}{(} \underset{1}{)} ,ドル $\underset{6}{(} \underset{3}{)} ,ドル $\underset{1}{(} \underset{3}{(} \underset{1}{)} \underset{3}{)} ,ドル $\underset{1}{(} \underset{3}{(} \underset{1}{)} \underset{6}{)} ,ドル $\underset{1}{(} \underset{6}{(} \underset{1}{)} \underset{3}{)} ,ドル $\underset{1}{(} \underset{6}{(} \underset{1}{)} \underset{6}{)} ,ドル $\underset{1}{(} \underset{6}{(} \underset{3}{)} \underset{6}{)} ,ドル $\underset{3}{(} \underset{1}{(} \underset{3}{)} \underset{6}{)} ,ドル $\underset{3}{(} \underset{6}{(} \underset{1}{)} \underset{6}{)} ,ドル $\underset{3}{(} \underset{6}{(} \underset{3}{)} \underset{6}{)} ,ドル $\underset{1}{(} \underset{6}{)} \underset{1}{(} \underset{3}{)} ,ドル $\underset{1}{(} \underset{6}{)} \underset{1}{(} \underset{6}{)} ,ドル $\underset{1}{(} \underset{6}{)} \underset{3}{(} \underset{1}{)} ,ドル $\underset{1}{(} \underset{6}{)} \underset{3}{(} \underset{6}{)} ,ドル $\underset{1}{(} \underset{6}{)} \underset{3}{(} \underset{1}{(} \underset{3}{)} \underset{6}{)} ,ドル $\underset{1}{(} \underset{6}{)} \underset{3}{(} \underset{6}{(} \underset{1}{)} \underset{6}{)} ,ドル $\underset{1}{(} \underset{6}{)} \underset{3}{(} \underset{6}{(} \underset{3}{)} \underset{6}{)} $의 21ドル$가지이다. 그러므로, 호출된 count 함수는 21ドル$을 반환해야 한다.

이 때, $\underset{1}{(} \underset{3}{(} \underset{3}{)} \underset{6}{)} $나 $\underset{6}{(} \underset{1}{(} \underset{3}{)} \underset{6}{)} $ 또한 뽑아낼 수 있으며 괄호의 형태만 보면 좋은 괄호열이지만, 각각 인접한 두 괄호의 색이 같은 경우와 짝지어진 두 괄호의 색이 같은 경우가 있으므로 알록달록한 괄호열이 아니다.

예제 3

색칠된 괄호열 $\underset{7}{(} \underset{1}{(} \underset{4}{)} \underset{1}{(} \underset{2}{)} \underset{6}{)} \underset{3}{(} \underset{4}{)} \underset{7}{)} \underset{5}{(} \underset{6}{)} \underset{2}{(} \underset{6}{)} \underset{5}{)} \underset{7}{)} $이 주어지면, 그레이더는 다음과 같이 함수를 호출한다.

count({ -7, -1, 4, -1, 2, 6, -3, 4, 7, -5, 6, -2, 6, 5, 7 })

호출된 count 함수는 1ドル,116円$을 반환해야 한다.

입력

출력

제한

• $P$의 길이를 $N$으로 나타낼 때, 1ドル \le N \le 700$
• 1ドル \le |P[i]| \le N$ (모든 0ドル \le i \le N - 1$)

서브태스크

힌트

샘플 그레이더

Sample grader의 입력 형식은 아래와 같다.

• Line 1: $N$
• Line 2: $P[0]$ $P[1]$ $\cdots$ $P[N-1]$

Sample grader의 출력 형식은 아래와 같다.

• Line 1: count 함수가 반환한 값

첨부

• colorful_public.zip