백준 11401번: 이항 계수 3 (Python)

접근

이 문제에 분할 정복 방법을 어떻게 적용해야 하나 고민하다가 결국 힌트를 찾아본 결과 '페르마의 소정리'를 이용한다는 것을 알게 되었다. 페르마의 소정리에 대해선 페르마의 소정리에서 개념 이해에 도움을 받았다.

이항 계수는 아래와 같은 식으로 구할 수 있는데, 분자와 분모를 모두 1,000,000,007로 나눌 경우 분모가 0이 되는 경우가 발생할 수 있기 때문에 페르마의 소정리 \( a^{p - 1} \equiv 1 (mod\ p) \) 를 이용하여 거듭제곱으로 표현하게 된다.

$$ \binom{n}{k}= _{n}\textrm{C}_{k} = \frac{n!}{(n - k)!k!} $$

$$ \frac{1}{(n-k)!k!}\%p = ({(n-k)!k!})^{-1}\%p = ((n-k)!k!)^{p - 2}\%p $$

$$ \because ((n - k)!k!)^{p-1} \% p = 1 $$

입력되는 n 크기의 팩토리얼 계산을 미리 해놓고, 이전 문제인 1629번: 곱셈 에서 사용한 거듭제곱을 빠르게 구하는 방법을 이용하여 본 계산을 빠르게 진행할 수 있다.

코드

import sys

n, k = map(int, sys.stdin.readline().split())
c = 1000000007


def power(a, b):  # 거듭제곱 구하는 함수
    b2 = []
    while b != 0:
        b2.append(b % 2)
        b //= 2
    a2 = [a % c]
    for i in range(1, len(b2)):
        a2.append(a2[i - 1] ** 2 % c)
    ans = 1
    for j in range(len(a2)):
        if b2[j] == 1:
            ans *= a2[j] * b2[j]
    return ans % c


# 팩토리얼 구하는 수식
fact = [1 for _ in range(n + 1)]
for i in range(2, n + 1):
    fact[i] = fact[i - 1] * i % c

a = fact[n]
b = (fact[n - k] * fact[k]) % c
print((a % c) * (power(b, c - 2) % c) % c)

더 생각해 볼 것

페르마의 소정리에 대한 완벽한 이해를 위해 다시 한번 확인할 필요가 있다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!