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

 

 

아이디어

 

모듈러 연산의 분배법칙과 페르마의 소정리로 계산식을 바꾼 후, 이분 탐색을 이용해 계산한다.

 

 

풀이

 

\(\binom{N}{K}\)는 \(\frac{N!}{K!(N-K)!}\)이고, \(\frac{N!}{K!(N-K)!}=\frac{N\cdot(N-1)\cdot\cdots\cdot(N-K+1)}{K!}\)이다.

 

결과값은 1,000,000,007로 나눈 나머지이므로 계산 과정에서 모듈러 연산의 곱셈에 대한 분배법칙을 이용할 수 있다.

\((a\bmod p)\cdot(b\bmod p)=ab\bmod p\)

따라서 계산 과정에서 발생하는 중간값들을 모두 1,000,000,007로 나눈 나머지로 두고 계산할 수 있다.

 

모듈러 연산의 곱셈에 대한 분배법칙으로 분모와 분자를 각각 1,000,000,007로 나눈 나머지로 계산하여 둔다.

그러나 모듈러 연산에서 나눗셈에 대한 분배법칙은 성립하지 않으므로,

분자를 분모로 나누는 대신 분자에 분모의 곱셈의 역원을 곱하여 계산하도록 한다.

 

페르마의 소정리에 따라 \(p\)가 소수이고 \(a\)가 \(p\)의 배수가 아니면 \(a^{p-1}\equiv 1\)이 성립하는데,

\(p\)는 1,000,000,007로 소수이고 분모 \(a\)는 1,000,000,007로 나눈 나머지이므로 항상 이 조건을 만족한다.

\(a^{p-1}\equiv 1\)에서 양변을 \(a\)로 나누면 \(a\cdot a^{p-2}\equiv a^{-1}\)가 되므로 \(a\)의 역원은 \(a^{p-2}\)이 된다.

 

분모의 역원을 구할 때에는 이분 탐색을 이용해 빠르게 계산하며 마찬가지로 모듈러 연산의 분배법칙을 이용한다.

 

def solution():

    def power(b, pw):
        if pw == 1:
            return b
        if pw%2:
            return ((power(b, pw//2)**2)*b)%p
        return (power(b, pw//2)**2)%p

    N, K = map(int, input().split())
    p = 1000000007
    if N-K < K:
        K = N-K
    num = den = 1
    for i in range(K):
        num = num*(N-i)%p
        den = den*(K-i)%p
    print(num*power(den, p-2)%p)

solution()

 

 

파이썬 내장 함수 pow()를 사용하여 거듭제곱을 계산할 수도 있다.

print(num*pow(den, p-2, p)%p)