테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 가희와 비행기 ======

===== 풀이 =====
  * 만약 고도가 항상 0 이상이 되어야 한다면, 대표적인 [[ps:카탈랑 수]] 문제가 된다
  * 여기에서는 처음과 끝을 제외하고는 항상 고도가 1 이상이 되어야 하는데, 이렇게 되려면 맨 처음에는 상승, 맨 마지막에는 하강이 와야 하고, 처음과 끝을 제외한 나머지만 따로 뽑아서 경로를 만들면 항상 0이상으로 유지되어야 한다. 즉 가운데의 d-2 길이의 경로가 뒤크 경로가 되는 가짓수를 구하면 되므로, 답은 (d-2)/2 번째 카탈랑수가 된다.
  * 모듈러스가 고정되 있지 않고 d보다 작은 경우도 가능하기 때문에, 원래 이런 경우를 효율적으로 계산하기 위해서는 [[ps:이항 계수#모듈러스가 n보다 작은 소수일 때|뤼카의 정리]]를 이용해서 이항계수를 구해야 한다. 하지만 d값 자체가 그렇게 크지 않다보니 그냥 정확한 이항계수 값을를 통째로 구한 다음에 나머지 연산을 해버리는 것이 오히려 빠르다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 22236. 가희와 비행기".

- Problem link: https://www.acmicpc.net/problem/22236
- Solution link: http://www.teferi.net/ps/problems/boj/22236

Tags: [catalan number]
"""

from teflib import combinatorics


def main():
    d, m = [int(x) for x in input().split()]
    print(combinatorics.catalan((d - 2) // 2) % m)


if __name__ == '__main__':
    main()

</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#catalan|teflib.combinatorics.catalan]]

{{tag>BOJ ps:problems:boj:골드_4}}