오늘의 한 마디
1,000,000,007으로 나눈 나머지 의 의미를 드디어 알았다!

• Baekjoon 문제 링크
• 현재 백준 문제집: 단기간 성장을 풀고 있습니다.

문제

자연수 $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

5 2

예제 출력 1

10

쉽게 말해서, $\binom{N}{K}\% 1,000,000,007$ 을 구하는 문제다.

---

발상

Try #1 : 그냥 $\binom{N}{K}$ 구하기

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

# nCk
# 4000000!를 구할 수 있어? 

dp = [1]*4000001
for i in range(2, 4000000):
    dp[i] = dp[i-1]*i % 1_000_000_007

print(dp[N] // (dp[K]*dp[N-K]) % 1_000_000_007)

위 공식을 그냥 구현한거다.
뭐... 당연히 이렇게 쉽게 맞을리가 없겠지만
시간 초과가 아니라 틀렸습니다가 나올 줄은 몰랐다.

---

몇 달전에 썼던 글인, 백준 #1629 곱셈에서 나머지 연산의 분배법칙에 대해서 공부했었다.

그래서 무의식적으로 나눗셈을 하더라도 나머지 연산의 분배법칙이 적용되지 않을까 생각했다.

print(dp[N] // (dp[K]*dp[N-K]) % 1_000_000_007)

위 부분이 아마 틀렸습니다의 원인이지 않을까 싶다.

이 글 중간부에 나오는 나머지 연산의 분배법칙 내용을 잠시 소개하자면,

(A+B) % p = ((A%p) + (B%p)) % p
(A-B) % p = ((A%p) - (B%p) + p) % p
(AxB) % p = ((A%p) x (B%p)) % p

하지만 나눗셈에 대해서는 분배법칙이 성립하지 않는다.
따라서 곱셈에 대한 분배법칙을 활용하기 위해, 분수 형태인 조합 공식을 곱셈의 형태로 바꿔주자.
이를 위해서 페르마의 소정리를 이용한다.

분수 형태인 조합 공식을 곱셈의 형태로 바꿔주자?
이를 위해서 페르마의 소정리를 이용한다?

Try #2 : 페르마의 소정리 이용

페르마의 소정리에 대해서 공부하면서,
드디어 오랫동안 백준에서 봐왔던 1,000,000,007의 역할을 알게 되었다.

공부하면서 적은 필기 내용을 백준 1,000,000,007의 의미 : 나머지 연산의 곱셈 역원, 페르마의 소정리라는 별도의 글로 포스팅하였다.

결론만 말하자면,

곱셈으로만 이루어졌기 때문에, 나머지 연산의 분배법칙을 적용하여 문제를 풀 수 있다.

1,000,000,005 제곱을 어떻게 할지 겁먹었을 지 모르지만,
분할 정복을 이용한 거듭제곱으로 풀면 그만이다.

$\log_{2}{1,000,000,005}=29.897...$

에 불과하다.

def power(a, b):
    if b == 0:
        return 1
    elif b == 1:
        return a
    
    tmp = power(a, b//2)
    if b%2 == 0:
        return tmp*tmp % 1_000_000_007
    return tmp*tmp*a % 1_000_000_007

그래서 1,000,000,005 제곱이 도대체 어디서 등장한 숫자냐 라는 의문이 든다면,
위에 소개한 별도 포스팅을 읽어보시길 추천한다.

---

풀이

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

def factorial(n):
    answer = 1
    for i in range(2, n+1):
        answer *= i
        answer %= 1_000_000_007
    return answer

def power(a, b):
    if b == 0:
        return 1
    elif b == 1:
        return a
    
    tmp = power(a, b//2)
    if b%2 == 0:
        return tmp*tmp % 1_000_000_007
    return tmp*tmp*a % 1_000_000_007

A = factorial(N)
B = factorial(N-K) * factorial(K) % 1_000_000_007
print(A * power(B, 1_000_000_005) % 1_000_000_007)