# 지금까지의 생각 ### 홀수는 안 됨 ### 짝수면 무조건 operation 2번 안에 올바른 괄호문자열 만들 수 있음 - 증명(엄밀하게는 못하겠음) - ( 를 +1, )를 -1로 보고 누적합을 그래프로 그린다. - 올바른 괄호문자열은 그래프가 0이하로 가지 않으면서 0으로 끝날때 - 적절히 1번 뒤집으면 그래프가 0이하로 가지 않게 할 수 있다. - 적절히 1번 뒤집으면 그래프가 그래프가 0에서 끝나게 할 수 있다. ### operation 1번이 최소인 경우는 양쪽끝이 한쪽 괄호로 되어 있는 경우다. - `(* A (*` 또는 `)* A )*` 꼴 (A는 올바른 괄호문자열) - 이건 확실하지 않은데 맞는거 같음 ### operatin 0번은 그냥 카탈란수 ### 정리하자면 어떠한 문자열이 있을 때 - 양쪽끝에 괄호를 추가해서 올바른 괄호문자열을 만들수 있으면 2번만에 가능 - 한쪽끝으로 괄호를 추가해서 올바른 괄호문자열을 만들 수 있으면 1번만에 가능 - 이미 올바른 괄호문자열은 0번만에 가능 --- ## 개수 세기 그럼 이제 카탈란수를 계산해서 전체식에 맞게 적절히 계산하면 됨. 0번인 경우는 $C(2n, n)$ 1번인 경우는 정리하니깐 $C(n+1, n/2-1)$ 2번인 경우는 $2^n - C(2n, n) - C(n+1, n/2-1)$ 그러면 전체식은 $3*2^n - 2*C(2n, n) - C(n+1, n/2-1) \mod m$ 근데 $1 \leq m \leq 10^9$라 m 이 소수도 아니라 페르마 소정리 안됨. [이항계수 6](https://www.acmicpc.net/problem/14854) 문제처럼 하는 방법이 있긴한데 맞는지 모르겠음 (소인수분해하고 CRT) ## 고민 - 위에 써져있는것들이 얼마나 맞는지 확실치 않음 - 마지막에 modular 처리를 어떻게 하는지 정확히 모르겠음 - 이항계수 6이 맞다면 좀 너무 어려운 스킬 - +@ 안자는 친구한테 물어보니깐 그냥 이항계수 6처럼하면 될것 같다해서 해봤는데 TLE