[Python] 백준 - 11401 이항 계수 3

문제

자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 4,000,000, 0 ≤ \(K\) ≤ \(N\))

출력

 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 출력한다.

 

 

필요한 도구

 

1. 페르마의 소정리 

2. 모듈러 연산 분배법칙(나눗셈은 적용 X)

3. 팩토리얼 연산 (3! = 1 x 2 x 3)

4. 거듭제곱 연산(분할정복)

 

문제해결방법

 

 

1. 다른 이항계수 문제와 다르게 주어지는 수가 굉장히 크다. 그냥 조합을 구하고, 나머지 연산을 하는 방법으로는 시간이 오래 걸릴 것을 예상할 수 있다.

 

2. 조합의 경우의 수를 구하는 공식은 다음과 같다. (0 ≤  K ≤ N일 때)

(조합과 페르마의 소정리에 대한 증명, 모듈러 연산의 분배법칙은 검색을 통해 쉽게 알 수 있다.)

 

 

3. 모듈러 연산의 분배법칙은 나눗셈의 경우 작동하지 않는다. 나눗셈의 꼴을 곱셈으로 변환시켜준다. 여기에 페르마의 소정리가 쓰인다.

 

4. 페르마의 소정리에 따르면, p가 소수일 때, 아래의 식과 같이 합동이다. 

5. 조합의 분모 부분의 식을 아래와 같이 바꾸어 줄 수 있다. 그리고 합동인 아래 식과 위 조합식의 분자 부분을 곱하면 된다는 걸 알 수 있다.

 

결과적으로 아래와 같은 꼴로 바꾸어 줄 수 있다.

 

 

이제 팩토리얼 함수와 큰 수일 때 효과적인 거듭제곱 함수를 이용해 코드를 작성하면 된다.

 

- 코드

import sys
input = sys.stdin.readline

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

def fac(int):
    res = 1
    for i in range(2, int+1):
        res *= i
        res %= p
    return res

def pow(a, b):
    if b == 1:
        return a % p
    else:
        t = pow(a, b//2)
        if b % 2 == 0:
            return (t**2) % p
        else:
            return (t**2*a) % p

a = fac(n)
b = fac(n-k)*fac(k)
print(a * pow(b, p-2) % p)