[BOJ] #11401 이항계수3 (Python)

 

 

 

1. 문제

11401번: 이항 계수 3

백준 11401 이항계수 3번 문제는 이항계수를 계산하는 문제입니다.

이항계수는 ${n \choose c}= \frac{n!}{r!(n - r)!}$ 공식을 이용하여 구할 수 있습니다. 문제에서 요구하는 답은 이 값을 1,000,000,007로 나눈 나머지를 출력하는 것입니다. 따라서 n, r, n-r의 팩토리얼 값을 DP로 계산합니다. 하지만 메모리 초과를 막기 위해서 팩토리얼 값을 그대로 저장하지 않고, 10000007로 나눈 값으로 저장할 것입니다. 그런데 이때 이항계수를 구하는 식에서는 그 팩토리얼 값이 분모로 들어가기 때문에 분모에 0이 들어가는 zero division 문제가 발생할 수 있습니다.

따라서 우리는 나눗셈 공식을 곱셈 공식으로 변환할 필요가 있습니다. 이때 페르마의 소정리를 이용합니다.

 

2. 페르마의 소정리

페르마의 소정리는 다음과 같습니다.

p가 소수이고 a가 p의 배수가 아닌 정수일 때,  $a^p \mod p = a \mod p$

따라서 위의 식에서 $(k!(n-k)!)^{-1} % p$를 $(k!(n-k)!)^{p-2} % p$로 바꿀 수 있습니다. 이러면 분모가 없어지고 곱셈으로만 표현될 수 있어서 zero division 문제를 없앨 수 있습니다.

${n!(k!(n-k)!)^{-1}} \mod 1000000007 = {n! \times (k!(n-k)!)^{1000000007-2}} \mod 1000000007$

 

3. 코드 작성

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 11401 이항계수3

import sys
input = sys.stdin.readline

div = 1000000007

def power(base, exponent):
    if exponent == 0:
        return 1
    if exponent == 1:
        return base

    x = power(base, exponent // 2)
    if exponent % 2 == 0:
        return x * x % div
    else:
        return x * x * base % div

n, k = map(int, input().split())
permutation = [1 for _ in range(n + 1)]

for i in range(2, n + 1):
    permutation[i] = (permutation[i - 1] * i) % div

print(int(permutation[n] * power(permutation[n - k] * permutation[k], div - 2) % div))