11386번 - 괄호 문자열

'('와 ')'로만 이루어진 문자열들을 괄호 문자열이라 하는데 괄호 문자열 중에서도 올바른 괄호 문자열은 아래와 같이 정의된다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. 문자열 S가 올바른 괄호 문자열이면 (S)도 올바른 괄호 문자열이다.
3. 문자열 S와 T가 올바른 괄호 문자열이면 ST도 올바른 괄호 문자열이다.

올바른 괄호 문자열이 아닌 괄호 문자열들은 올바르지 않은 괄호 문자열이라고 한다. 올바른 괄호 문자열의 예로는 "(())()", "()()()", "(()())” 등이 있고, 올바르지 않은 괄호 문자열의 예로는 "())(()", "(", "(()()()" 등이 있다.

어떤 문자열 S가 주기성이 있는 문자열이라는 것은 문자열 S의 비어 있지 않은 접두사 u가 동시에 S의 접미사일 때가 있음을 뜻한다. 주기성이 있는 문자열이 아닌 문자열들은 주기성이 없는 문자열이라고 한다. 주기성이 있는 문자열의 예로는 "abcabcab", "()(", "aaaaaa" 등이 있고, 주기성이 없는 문자열의 예로는 "abcd", "(())()", "a" 등이 있다. 각각 두 번째로 들었던 예는 주기성이 있는 괄호 문자열과 주기성이 없는 괄호 문자열이라고 할 수 있다.

길이가 L인 괄호 문자열들 중에서 주어진 조건을 만족하는 개수를 구하는 프로그램을 작성하시오.

첫 번째 줄에 네 정수 p, q, m, Q (0 ≤ p, q ≤ 1, 1 ≤ m ≤ 10⁶, 1 ≤ Q ≤ 10⁵)이 공백을 사이로 두고 차례대로 주어진다.

다음 Q개의 각 줄에는 하나의 자연수 L (1 ≤ L ≤ 10⁶)이 주어진다. 앞으로 길이가 L인 모든 괄호 문자열의 집합을 A_L, 길이가 L인 올바르지 않은 괄호 문자열의 집합을 B_L, 길이가 L인 주기성이 없는 괄호 문자열의 집합을 C_L이라고 하자. 주어지는 각 L마다 p = 0이면 P = A_L, p = 1이면 P = B_L이고, q = 0이면 Q = A_L, q = 1이면 Q = C_L이다. 여러분은 P ∩ Q의 크기를 m으로 나눈 나머지를 출력해야 한다.

즉 p = 1, q = 0이면 길이가 L인 올바르지 않은 괄호 문자열의 개수를, p = 0, q = 1이면 길이가 L인 주기성이 없는 괄호 문자열의 개수를, p = 1, q = 1이면 길이가 L인 올바르지 않으면서 주기성도 없는 괄호 문자열의 개수를 구하면 된다.

Q개의 줄에 걸쳐서 입력에서 정의한 대로 P ∩ Q의 크기를 m으로 나눈 나머지를 출력하면 된다.

길이가 4인 괄호 문자열 중에서 올바른 것은 "()()"과 "(())"의 두 가지이므로, 올바르지 않은 괄호 문자열의 개수는 16 - 2 = 14개 이다. 그리고 길이가 4인 주기성이 없는 괄호 문자열은 "((()", "(())", "()))", ")(((", "))((", ")))("의 6개이고, 이 중에서 올바른 괄호 문자열은 "(())" 하나이므로, 길이가 4인 올바르지 않으면서 주기성도 없는 괄호문자열은 5개이다.