ps:카탈랑_수
카탈랑 수 (Catalan number)
- 카탈란 수라고 표기하는 책도 많은 것 같은데, 여기서는 위키피디아를 따라서 카탈랑수로 표기한다
- 올바른 괄호의 갯수를 비롯 많은 문제의 해가 카탈랑 수로 표현된다.
- 그 문제들에 대해서 DP적인 마인드로 접근하면 이런 점화식을 얻는다
- $ \begin{align} &C_0 = 1 \\ &C_{n+1} = \sum_{i+j=n} C_iC_j \end{align}$
- 이대로 점화식대로 계산해서 풀려면 O(n^2)이지만, 점화식을 잘 변환하면 다음처럼 식이 정리된다.
- 이렇게 이항 계수 형태의 식을 이용하면 Cn을 O(n)에 구할 수 있다. Cn % P 를 구하는 것도 O(n + logP)에 가능. 자세한 것은 이항 계수참고.
- 만약 1≤i≤n 까지의 모든 Ci를 구해야 할 경우에는 $ C_{n+1} = \frac{2(2n+1)}{n+2}C_n $ 의 점화식을 사용해서 여전히 O(n)에 모두 구할 수 있다. Ci % P를 구하는 경우도, n 이하의 모든 수의 모듈러 역원을 O(n)에 구하는 방법을 사용하면, 여전히 O(n)에 계산 가능하다.
inv = [0, 1] for i in range(2, MAX_SIZE + 3): inv.append(-(MOD // i) * inv[MOD % i]) catalan_nums = [1] for i in range(MAX_SIZE): catalan_nums.append(2 * (2 * i + 1) * inv[i + 2] * catalan_nums[i] % MOD)
관련 문제
- 올바른 괄호의 갯수 - 그냥 카탈랑 수를 계산한다
- 괄호 - 1≤i≤n 까지의 모든 카탈랑 수를 구한다.
ps/카탈랑_수.txt · 마지막으로 수정됨: 2021/01/21 15:37 저자 teferi
토론