[백준 11401 파이썬] 이항 계수 3 (골드1, 분할 정복)

알고리즘 유형 : 분할 정복
풀이 참고 없이 스스로 풀었나요? : X

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

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

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

# 거듭제곱 계산(나머지 연산 적용)
def square(n, k):
    if k == 0:
        return 1
    elif k == 1:
        return n
    
    tmp = square(n, k//2)
    if k % 2:
        return tmp * tmp * n % p
    else:
        return tmp * tmp % p

top = factorial(N)
bot = factorial(N-K) * factorial(K) % p

# 페르마의 소정리 이용해서 조합 공식 곱셈 형태로 변형
print(top * square(bot, p-2) % p)

풀이 요약

1. $_{n}\mathrm{C}_{k}$ 값을 1000000007로 나눈 나머지를 구하는 문제

2. 재귀 팩토리얼, 파스칼 삼각형 DP는 활용 못함. 전자는 스택 오버플로, 후자는 최대 연산이 4000000 깊이의 파스칼 삼각형을 채우는 연산 수 4000000(1+4000000) = 대략 16조, TLE(시간 초과)

3. $_{n}\mathrm{C}_{k}$ = N! / (N-K)!K! 이다.

4. 우선, 나머지 연산(모듈로 연산)의 분배법칙에 대해 알아보자.

   (A + B) % p = ((A % p) + (B % p)) % p

   (A x B) % p = ((A % p) x (B % p)) % p

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

   나눗셈에 대해서는 분배법칙이 성립하지 않는다. 따라서, 곱셈에 대한 분배법칙을 활용하기 위해,

   분수 형태인 조합 공식을 곱셈의 형태로 바꿔주자.

   이를 위해서 페르마의 소정리를 이용한다.

   
   <페르마의 소정리>

   p가 소수, a가 정수일 때

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

   세 줄 등호는 합동을 의미한다. (p로 나눈 나머지가 서로 같다)

   이 식의 양 변을 a^2로 나눠주면

   $a^{p-2}\, \equiv \, \frac{1}{a}\, (mod\ p)\ \left(a\ \ne 0\right)$

   이를 이용하면 된다.

5. 조합 공식을 곱셈 형태로 변형해준다. (a^-1는 a^(p-2)와 합동)

   ${\ }_N{C}_K\ \%\ p\ =\ \frac{N!}{\left(N-K\right)!K!}\ \%\ p\ =\ N!{\left(\left(N-K\right)!K!\right)}^{-1}\ \%\ p$

   $=\ N!{\left(\left(N-K\right)!K!\right)}^{p-2}\ \%\ p$

6. 이제 구현을 해보자.

   팩토리얼은 1부터 N까지 for 돌면서 %p 연산 해주고 N! % p 를 리턴하는 함수를 정의해주자.

   이를 이용해서 분자와 분모를 하나의 값, top과 bot 변수에 구해놓자.(나머지 연산이 적용된 값이 담겨있음)

   이 후 분할 정복 거듭제곱 함수를 정의하고, bot^(p-2)를 %p 연산 적용된 값으로 구할 때 써먹는다.

   그리고는 top과 (bot^(p-2) % p)(여기서 거듭제곱 함수 활용) 를 곱하고 한번 더 %p를 해주면 구하는 답이 된다.

배운 점, 어려웠던 점

• 모듈로 연산의 합, 차, 곱에 대한 분배법칙을 알게 되었다.

• 페르마의 소정리에 대해 알게 되었다. 이 문제는 이게 핵심이라고 생각한다.

  페르마의 소정리를 활용하여 분수 형태를 곱셈 형태로 바꾸고 모듈로 연산의 곱에 대한 분배법칙을 활용하는 것!