[파이썬] 11401번. 이항 계수 3 풀이

간단하게 nCk -> n!/k!(n-k)! 같은 방식으로 문제를 풀 수 없다.

문제의 N과 K가 매우 크기 때문에 기존의 팩토리얼 알고리즘은 시간/공간 복잡도를 초과한다.

 

하지만 문제에서는 nCk 값을 1,000,000,007로 나누라고 했으므로 나머지를 구하는 소수(P)가 주어졌다.

 

그러면 페르마의 소정리를 적용할 수 있다. 자세한 것은 생략하지만, 조합 공식을 곱셈 형태로 변형할 수 있다.

∴ nCk​ % P = n! x ((n−k)!k!)^P−2 % P 

 

여기서도 n, k, n-k의 팩토리얼을 그대로 구할 수 없기 때문에, 나머지 연산을 적용한 팩토리얼을 구하기 위해서

나머지 연산의 분배법칙 중 곱셈에 대한 분배법칙을 사용하면 된다!

(A x B) % P = ((A % P) x (B % P)) % P

 

즉, A에 해당하는 n!를 P로 나머지 연산하면서 구하고,

B에 해당하는 (k!(n-k)!)^P-2 도 P를 나머지로 한 분할 정복을 이용한 거듭제곱을 이용하면 된다!

 

"분할 정복을 이용한 거듭제곱"은 여기서 참고할 수 있다.

2023.09.07 - [파이썬 알고리즘/백준 25단계] - [파이썬] 1629번. 곱셈 풀이

[파이썬] 1629번. 곱셈 풀이

 

---

# 팩토리얼 값 계산 (나머지 연산 적용)
def factorial_with_rest(N, rest):
    n = 1
    for i in range(2, N+1):
        n = (n * i) % rest
    return n

# 거듭제곱 계산 (나머지 연산 적용)
def reduce_pow(a, b, c):
    if (b == 1):
        return a % c

    X = reduce_pow(a, b//2, c)

    if (b % 2 == 0): # 짝수라면
        return X * X % c
    else: # 홀수라면
        return a * X * X % c


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

first = factorial_with_rest(N, P)
second = factorial_with_rest(K, P) * factorial_with_rest(N-K, P)

print(first * reduce_pow(second, P-2, P) % P)