백준 11401: 이항 계수 3 (파이썬)

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

11401번: 이항 계수 3

---

코드

#https://teching.tistory.com/

n, k = map(int, input().split())
mode = 1_000_000_007

def pastPow(a, b, c):
    if b == 0:
        return 1
    elif b == 1:
        return a % c
    else:
        DivCon = pastPow(a, b // 2, c)
        if b % 2 == 0:
            return (DivCon * DivCon) % c
        else:
            return (DivCon * DivCon * pastPow(a, 1, c)) % c


fac = [1, 1] + [1] * (n - 1)
for i in range(1, n + 1):
    fac[i] = (fac[i - 1] * i) % mode
answer = (fac[n] * pastPow((fac[k] * fac[n - k]) % mode, mode - 2, mode)) % mode
print(answer)

해설

나머지연산(모듈러연산)을 처리해야하는 문제이다.

모듈러 연산은 다른 사칙연산(더하기, 빼기, 곱하기)에 대해서는 분배법칙이 모두 통하는데 오직 나머지연산에서는 분배법칙이 통하지 않는다.

즉, (a/b) % p는 (a%p)/(b%p)와 값이 같지 않다는 것이다. 따라서 이 문제점을 해결하기 위해서는 나눗셈을 곱셈으로 바꾸어서 (a%p * (b^-1)%p)와 같은 모습으로 바꾸어 주어야 한다.

나눗셈을 곱셈으로 바꾸기 위해서는 페르마의 소정리를 이용해야한다.

우리는 이러한 페르마의 소정리에 양변을 a로 나누어 주면 a^(p-2) ≡ a^-1 (mod p) 으로 바꾸어 낼 수 있다.

 

따라서 이항 계수

nCk mod p

= (n! / k!(n-k!)) mod p

= ( (n! mod p) / (k!(n-k)! mod p) ) mod p

≡ ( (n! mod p) * ( (k!(n-k)!) ^ (p -2) )mod p )  mod p

으로 바꿀 수 있는 것이다. 

 

여기서 거듭제곱은 이전에 풀었던 https://teching.tistory.com/119 해당 문제에서 사용한 방법을 사용하고

백준 1629: 곱셈 (파이썬)

팩토리얼을 구하는 것은 DP를 이용해 구현을 했다