[Python] 9343번 랜덤 걷기

 

https://www.acmicpc.net/problem/9343

9343번: 랜덤 걷기

---

 

23/12/07

 

 

누가 봐도 그냥 카탈란 수 문제다.

---

 

문제 접근 방식:

 

 

누가 봐도 그냥 카탈란 수 문제인데, 이건 제한이 크기 때문에 카탈란 수의 점화식으로 구현하면 안된다.

 

일반항으로 접근해야 되는데, 모듈로 역원을 활용하여 구현할 수 있다.

 

파이썬은 모듈로 역원을 pow함수를 통해 쉽게 구할 수 있으니 이를 잘 활용해 보자.

 

카탈란 수의 일반항은 다음과 같다.

 

$$C_n = \frac{1}{n+1} \binom{2n}{n}$$

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

 

# 9343번 랜덤 걷기
# DP, 조합론
'''
접근 방법:
카탈란 수
'''
import sys
input = sys.stdin.readline

MOD = 1_000_000_000+7
fac = [-1 for _ in range(2_000_000 + 1)]
fac[0] = 1
for i in range(1, 2_000_000 +1):
    fac[i] = (fac[i-1]*i)%MOD
def comb(n, r):
    if n < r:
        return 0
    return (((fac[n]*modInverse(fac[r], MOD))%MOD)*modInverse(fac[n-r], MOD))%MOD
def modInverse(a, m): # m이 소수인 경우
    return pow(a, m-2, m)
def Catalan(n):
    return (comb(2*n, n)*modInverse(n+1, MOD))%MOD
for _ in range(int(input())):
    N = int(input())
    print(Catalan(N))