가희와 비행기

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

"""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()

• Dependency: teflib.combinatorics.catalan