$_nC_k$를 $1e9+7$로 나눈 나머지를 빠르게 구해보자. $(n \leq 4,000,000)$

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

$_nC_k$를 수식으로 풀어 쓰면 다음과 같다.

$$ \frac{n!}{(n-k)! \ k!} $$

위의 $n!$은 $1$부터 $n$까지 곱해주면서 $mod$를 해주면 구할 수 있다. 그러면 분모에 있는 $(n-k)! \ k!$을 어떻게 처리해야 할까? 페르마의 소정리 공식을 살펴보자.

$$ a^p \equiv a \ (mod \ p) $$

위 공식에서 $p$는 소수이다. 위 공식을 조금 변형하면 다음과 같은 식을 만들 수 있다.

$$ a^{p-2} \equiv a^{-1} \ (mod \ p) $$

이제 우리는 $a$의 자리에 $(n-k)! \ k!$을 넣어주면 $((n-k)! \ k!)^{-1}$을 $p$로 나눈 값을 구해 줄 수 있다. $a^{p-2}$은 분할정복을 이용한 거듭제곱으로 $\mathcal{O}(logN)$ 시간에 구해줄 수 있다.

위 문제의 정답코드는 아래와 같다.

n,k = map(int, input().split())
mod = 1000000007

def fac(n):
    result = 1
    for i in range(2,n+1):
        result = (result*i)%mod
    return result

def power(n,cnt):
    if cnt == 1:
        return n
    
    div = power(n,cnt//2)
    if cnt&1:
        return (div*div*n)%mod
    else:
        return (div*div)%mod

print((fac(n)*power((fac(n-k)*fac(k)),mod-2))%mod)