Atcoder Japanese Student Championship 2019 Qualification - C(Cell inversion)

문제 링크

atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c

C - Cell Inversion

관찰 1)

(a, b) (c, d)와 (a, d) (b, c)의 효과는 같다.

관찰 2)

S가 주어진다면, 그 S에서 화살표의 왼 부분이 될 문자들과, 오른 부분들이 될 문자들은 이미 정해져있다.

index가 짝수번째이면서 B이거나, 홀수번째이면서 W이면 언제나 화살표의 왼쪽이 배정되고 (괄호문자열의 "(") 반대 경우는 언제나 화살표의 오른쪽이 배정된다. (괄호문자열의 ")")

 

고로 이 문제는 괄호문자열이 주어졌을 때, 각 "("와 ")"를 매칭하는 가짓수를 묻는 문제와 같아진다.

 

마지막에는 n!을 곱해주어야한다. (n회 시행)