[백준] / [Python] / [11401] 이항 계수 3

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

11401번: 이항 계수 3

---

문제

자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 4,000,000, 0 ≤ \(K\) ≤ \(N\))

출력

 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 출력한다.

---

이 문제는 스스로 풀지 못하였고, 블로그를 참고하였습니다.

 

1. \(_{n}\mathrm{C}_{k}\) = \(N! / (N-K)!K!\)

2. 나머지 연산(모듈러(Modulo) 연산)의 분배법칙에 대해 알고 있어야 합니다.

    (A + B) % p = ((A % p) + (B % p)) % p

    (A x B) % p = ((A % p) x (B % p)) % p

    (A - B) % p = ((A % p) - (B % p) + p) % p

    \(\rightarrow\) 모듈러 연산은 나눗셈에 대해서는 분배법칙이 성립하지 않습니다. 따라서 곱셈에 대한 분배법칙을 활용하기 위해

    분수 형태인 조합 공식을 곱셈의 형태로 바꿔줍니다. 이를 위해서는 페르마의 소정리를 사용해야 합니다.

  

    페르마의 소정리 (Fermat's little Theorem)

    \(p\)가 소수이면, 모든 정수 \(a\)에 대해 \(a^p \equiv a \pmod{p}\)이다. (\(\equiv\) 는 합동(\(p\)로 나눈 나머지가 같다.) 이다.)

    \(p\)가 소수이고 \(a\)가 \(p\)의 배수가 아니면, \(a^{p-1} \equiv 1 \pmod{p}\)이다.

   위 정리에서 양 변을 \(a^2\)로 나눠주면, \(a^{p-2} \equiv {1 \over a} \pmod{p} (a \ne 0)\) 을 이용하면 된다.

 

3. 즉, 나머지 연산 분배법칙 + 페르마의 소정리를 활용하여

    \((A / B) \% p = (A*B^{p-2}) \% p = ((A\%p)*(B^{p-2} \% p )) \% p\) 처럼 나타낸다. 이를 조합에 적용하면, 

    \( _{n}\mathrm{C}_{k}\) \(\% p = \frac{N!}{(N-K)!K!} \% p = {N!((N-K)!K!)}^{-1} \% p = N!{((N-K)!K!)}^{p-2} \% p\) 와 같이 나타낼 수 있다.

---

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
p = 1000000007

# 팩토리얼
def factorial(N):
    n = 1
    for i in range(2, N+1):
        n = (n * i) % p
    return n

# 거듭제곱 계산(나머지 연산 적용)
def power(a, b):
    if b == 0:
        return 1
    if b % 2:    #홀수이면
        return (power(a, b//2) ** 2 * a) % p
    else:    #짝수이면
        return (power(a, b//2) ** 2) % p

top = factorial(N)
bot = factorial(N-K) * factorial(K) % p

# 페르마의 소정리 이용해서 조합 공식 곱셈 형태로 변형
print(top * power(bot, p-2) % p)