[백준 알고리즘] 이항계수3(11401)

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

이번 문제는 11050, 11051번 문제와는 달리 굉장히 큰 입력을 처리해야 합니다.

특히 ( 큰 수 / 큰 수 ) 를 실행해야 하는데 이는 쉽지 않으므로 간단한 방법을 생각해보겠습니다.

$$_{n}C_{k}\textrm{ mod }1000000007 = \frac{n!}{k!(n-k)!}\textrm{ mod 1000000007}$$

이 식을 풀어야 하는데 단순히 큰 수끼리의 나눗셈이 힘들기 때문에 페르마의 소정리를 이용한 분할정복법을 이용하겠습니다.

페르마의 소정리를 이용하여 위 식을 변형하기 위해서는 나머지연산 곱셈의 역원에 대해서 알아야 합니다.

분할정복

분할 정복법(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트 나 합병정렬이 있다.  

(출처 : https://namu.wiki/w/%EB%B6%84%ED%95%A0%20%EC%A0%95%EB%B3%B5%EB%B2%95)

페르마의 소정리

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

p가 소수이고 a와 p가 서로수라면 a^(p-1)을 p로 나눈 나머지는 1이다.

나머지연산 곱셈의 역원

곱셈의 역원이란  ax = xa = 1에서 a의 곱셈에 대한 역원을 x라고 합니다.

그렇다면 나머지연산에서는 위의 식을 조금만 변형하면 됩니다.

$$ax \equiv xa\equiv 1(mod\textrm{ m})$$

페르마의 정리를 이용하여 위와 같은 식을 만들어보겠습니다.

$$\begin{align*} a^{p-1}\equiv 1\\ a\times a^{p-2}\equiv 1\\ a\times x\equiv 1\\ \therefore x=a^{p-2} \end{align*}$$

이처럼 페르마의 소정리를 이용하면 나머지연산 곱셈의 역원은 a^(p-2)이라는 것을 알 수 있습니다.

변형된 nCk 나머지 연산

페르마의 소정리를 이용하여 변형된 식을 이용하면 nCk의 나머지를 구할 수 있습니다.

나누는 수인 1,000,000,007을 m이라고 하겠습니다.

$$\frac{n!}{k!(n-k)!}\textrm{ mod m }$$

위 식을 다르게 mod 대신에 모듈러 기호를 이용하여 표현합니다.

$$\equiv n!\times \frac{1}{k!(n-k!)}$$

위 식에 우리가 구한 

$$(\left [ k!(n-k)!\times (k!(n-k!))^{m-2} \right ]\equiv 1)$$

을 양변에 곱합니다. (쉽게  생각하면 양변에 1을 곱한 것이라고 생각할 수 있습니다.

$$n!\times \frac{1}{k!(n-k)}\times \left [ k!(n-k)!\times (k!(n-k!))^{m-2} \right ]\equiv \left [ k!(n-k)!\times (k!(n-k!))^{m-2} \right ]\times x$$

위 식을 약분하여 정리하면

$$n!\times (k!(n-k)!)^{m-2}\equiv x$$

이라는 식을 구할 수 있습니다.

위 식을 이용하면

$$[n!\times (k!(n-k)!)^{m-2}]\textit{ mod m }= (n!\textit{ mod m })\times [(k!(n-k)!)^{m-2}\textit{ mod m }]$$

이라는 식도 얻을 수 있습니다.

이제 이 식을 파이썬코드로 구현하겠습니다.

m = 1000000007

def x_y(x, y):
    xy = 1
    while y > 0:
        if(y % 2) == 1:
            xy *= x
            y -= 1
            xy %= m
        x *= x
        x %= m
        y /= 2
    return xy

x_y(x, y) 함수는 거듭제곱을 계산하는 함수입니다.

그런데 거듭제곱수만큼 곱하는 것이 아니라 시간복잡도를 줄이기 위해서 

$$a^{10} = (a^{5})^{2} = (a\times (a^{2})^{2})^{2}$$

와 같은 방법을 이용했습니다.

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

r1 = 1
r2 = 1

for i in range(1, N+1):
    r1 *= i
    r1 %= m

for i in range(1, K+1):
    r2 *= i
    r2 %= m

for i in range(1, N-K+1):
    r2 *= i
    r2 %= m

입력 값을 각각 N, K에 저장합니다.

r1에는 분자 부분이 될 N!을 계산합니다.

r2에는 분모 부분이 될 K!(N-K)!을 계산합니다.

여기서 단순히 팩토리얼 계산만 하는 것이 아니라

$$(a\times b)\textit{ mod m }=(a\textit{ mod m })\times (b\textit{ mod m })$$

의 방법을 이용해서 수가 커지는 것을 방지합니다.

r2 = x_y(r2, m-2)
r2 %= m
r1 *= r2
r1 %= m
print(r1)

$$n!\times (k!(n-k)!)^{m-2}\equiv x$$

마지막으로 이 식을 이용하여 나머지를 구한 후 출력하면 되겠습니다.

m = 1000000007

def x_y(x, y):
    xy = 1
    while y > 0:
        if(y % 2) == 1:
            xy *= x
            y -= 1
            xy %= m
        x *= x
        x %= m
        y /= 2
    return xy

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

r1 = 1
r2 = 1

for i in range(1, N+1):
    r1 *= i
    r1 %= m

for i in range(1, K+1):
    r2 *= i
    r2 %= m

for i in range(1, N-K+1):
    r2 *= i
    r2 %= m

r2 = x_y(r2, m-2)
r2 %= m
r1 *= r2
r1 %= m
print(r1)