---
# System prepended metadata

title: 지금까지의 생각

---

# 지금까지의 생각

### 홀수는 안 됨

### 짝수면 무조건 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

