Yukicoder No. 1873 Bracket Swapping

No. 1873 Bracket Swapping

문제 링크

제한

• 시간 제한: 2초
• 메모리 제한: 512MB

문제

올바른 괄호 문자열 $S$와 음이 아닌 정수 $K$가 주어집니다. $S$에 대해 다음 조작을 $K$번 반복한 이후의 $S$가 올바른 괄호 문자열이 되는 경우의 수를 $998244353$으로 나눈 나머지를 구해주세요.

• $1 \le i < j \le |S|$를 만족하는 정수 $(i, j)$를 고른다. $S$의 $i$번째 문자와 $j$번째 문자를 교환한다.

단, 어떤 정수 $l$ ($1 \le l \le K)$가 존재해서 $l$번째 고른 $(i, j)$가 다른 경우, 또한 그 경우에 한해서 두 조작방법을 다르다고 합니다.

올바른 괄호 문자열의 정의

다음을 만족하는 괄호 문자열을 올바른 괄호 문자열이라 정의합니다.

• 빈 문자열
• 어떤 올바른 괄호 문자열 $A$가 존재해서, (, $A$, )을 순서대로 연결한 문자열
• 어떤 비어있지 않은 두 올바른 괄호 문자열 $A$, $B$가 존재해서, $A$, $B$를 순서대로 연결한 문자열.

입력

$S$  $K$

• $S$는 올바른 괄호 문자열
• $2 \le |S| \le 200$
• $0 \le K \le 10^9$

출력

정답을 출력해주세요.

예제

예제 1

입력

(())
1

출력

3

처음 조작으로 $(i, j) = (1, 2), (2, 3), (3, 4)$를 고를 경우 조건을 만족합니다.

예제 2

입력

()
100

출력

1

예제 3

입력

(()(()(())()))
924844033

출력

392727613

$998244353$으로 나눈 나머지를 출력합니다.

풀이

기본적인 아이디어는 가능한 모든 올바른 괄호 문자열 $T$에 대해, $S$에서 $T$로 바꿀 수 있는 경우의 수를 모두 합해주는 것입니다. 그냥 구현하면 시간이 매우 오래 걸리기 때문에 다음과 같은 아이디어를 사용합니다. 일단 기호를 정의합시다.

• $d(S, T)$를 $S$와 $T$의 서로 다른 문자의 개수, 즉 $s_i \ne t_i$ 인 $i$의 개수로 정의합니다.
• $f(T, k)$를, $S$를 $k$번 조작해서 $T$로 만들 수 있는 경우의 수라고 정의합시다.

여기서, 다음이 성립합니다.

• 여는 괄호와 닫는 괄호의 개수가 같은 괄호 문자열 $T_1, T_2$에 대해 $d(S, T_1) = d(S, T_2)$이면, $f(T_1, k) = f(T_2, k)$입니다.

증명은, $S_i = S_{\varphi(i)}$이고, $T_{1,i} = T_{2,{\varphi(i)}}$인 순열 $\varphi$를 생각해 봅시다. 해당 순열이 존재하는 이유는, $S_i$가 여는 괄호인 $i$에 대해 $T_{1,i}$의 여는 괄호 개수와 $T_{2,i}$의 여는 괄호 개수가 같기 때문입니다.

이 때, 문자열 $S$를 $T_1$으로 만드는 조작 $(i_1, j_1), \cdots, (i_k, j_k)$에 대해, $(\varphi(i_1), \varphi(j_1)), \cdots, (\varphi(i_k), \varphi(j_k))$는 문자열 $S$를 $T_2$로 만드는 조작입니다.

두 조작사이에 일대일대응이 존재하고, 두 경우의 수는 같습니다.

 

그래서, $d(S, T)$에 따라 $T$를 묶어서, 경우의 수와 개수를 따로 세어 줄 것입니다.

 

• 경우의 수

$S$를 $i$번 조작해서 $d(S, T)$가 $2j$가 되는 경우의 수를 $D_{i, j}$라고 합시다.

$j$가 $1$ 늘어나는 경우는, 원래 올바른 괄호쌍을 올바르지 않게 바꾸는 경우이기 때문에, $D_{i+1, j+1}$에는 $D_{i, j}$에서 $(|S|/2-j)^2$만큼을 곱한 값을 더합니다.

$j$가 $1$ 줄어드는 경우는, 원래 올바르지 않은 괄호쌍을 올바르게 바꾸는 경우이기 때문에, $D_{i+1, j-1}$에는 $D_{i, j}$에서 $j^2$만큼을 곱한 값을 더합니다.

다른 경우에는 $j$가 줄어들지 않기 때문에, $D_{i+1, j}$에는 $D_{i, j}$에서 $|S|(|S|-1) - (|S|/2-j)^2 - j^2$만큼을 곱한 값을 더합니다.

그리고, $D_{K, *}$ 이 우리가 구하고자 하는 값입니다.

이것을 그냥 구할 경우에 $O(K|S|)$ 시간이 걸리기 때문에, 행렬 제곱을 이용해서 $O(|S|^3 \log K)$ 시간이 걸리도록 계산하면 $D_{K, *}$을 구할 수 있습니다.

• 개수

$E_{i, j, k}$를 길이가 $i$인 괄호 문자열 중에서, 뒤에 $j$개의 괄호를 닫으면 올바른 괄호 문자열이 되며, $S$와 $k$개가 다른 경우의 수라고 정의합시다.

$i$ 번째 문자로 여는 괄호를 고르는 경우, $i$, $j$가 $1$ 증가하고, $k$는 $S_i$가 여는 괄호인지의 여부에 맞게 증가 혹은 유지합니다. 닫는 괄호일 때는 $i$가 $1$ 증가, $j$가 $1$ 감소하고, $k$는 $S_i$가 닫는 괄호인지의 여부에 맞게 증가 혹은 유지합니다. $j$가 음수인 경우를 제외하고, 동적 계획법 테이블을 계산해줍니다.

이를 이용해서 동적 계획법 테이블을 채워나가면 $O(|S|^3)$ 시간이 걸리도록 계산할 수 있습니다.

 

최종적으로 우리가 계산해야할 답은, 괄호의 개수 차이가 $i$개 나는 올바른 괄호 문자열의 개수 $E_{N, 0, i}$와, 해당 괄호 문자열을 만드는 경우의 수 $D_{K, i} / {|S|/2 \choose i}^2$을 $i$마다 곱해 합한 값입니다. 여기서, ${|S|/2 \choose i}^2$ 으로 나누는 이유는, $d(S, T) = i$ 인 여는 괄호와 닫는 괄호의 개수가 같은 괄호 문자열 $T$가 ${|S|/2 \choose i}^2$개 존재하기 때문입니다.

 

구현: https://yukicoder.me/submissions/745717