직장인의 개발 일기

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

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다.

https://rudalsd.tistory.com/61?category=1064608 

먼저 $\binom{N}{K}$는 다음과 같이 나타낼 수 있습니다.

$\binom{N}{K} = \frac{N!}{(N-K)!K!}$

그리고 페르마의 소정리를 이용하여 mod $m$에서 어떤 수를 $a$로 나눈다는 뜻은 $a$의 역원을 곱한다는 뜻과 같습니다. 따라서 $m$이 소수일 때, $a^{m-1}\equiv 1($mod $m)$이고, $a\times a^{m-2}\equiv 1($mod $m)$이므로 mod $m$에서 $a$에 대한 곱셈의 역원은 $a^{m-2}$입니다.

따라서, 

$\frac{N!}{(N-K)!K!} \equiv N!\times ((N-K)!K!)^{m-2}($mod $m)$

이 됩니다.

분모의 수로 나누는 방법 대신 $m-2$제곱한 값을 곱해주면 모듈러 연산 시 같은 결과가 나오는 것을 알 수 있습니다.

이 때 $m$의 값이 $1,000,000,007$로 매우 크므로 분할 정복을 이용한 거듭제곱을 이용하여 문제를 풀어주면 됩니다.

[ 소스 코드 ]

페르마의 소정리(Fermat's little theorem)는 다음과 같이 정리할 수 있습니다.

$a\geq 0$에 대하여 $a^{p}\equiv a($mod $p)$를 만족하고,

만약 $p$가 소수이고, $a$와 $p$가 서로소이면 $a^{p-1}\equiv 1($mod $p)$를 만족한다.

수학적 귀납법을 이용하여 위의 식을 증명해보겠습니다.

먼저, $0\leq a\leq p-1$ 범위의 정수에서만 증명해도 충분합니다. 그 이유는 $a$를 $p$로 나눈 나머지는 항상 $0$보다 크거나 같고 $p-1$보다 작거나 같기 때문입니다.

1. $a = 0$일 때

$a$가 $0$인 경우에는 $0^{p} = 0\equiv 0(mod$ $p)$

2. $a = k$일 때 성립한다고 가정하고 $a = k+1$일 때

$a=k$일 때 성립한다고 가정했으므로, $k^{p}\equiv k(mod$ $p)$를 만족합니다.

이항 정리를 사용하여 $a = k + 1$일 때도 성립함을 증명합니다.

$(k+1)^{p}=\sum_{i=0}^{p}\binom{p}{i}k^{i}$

이때 이항 계수의 정의에 의해서

$\binom{p}{i} = \frac{p!}{(p-i)!i!}=\frac{p(p-1)\cdot \cdot \cdot(p-i+1)}{i(i-1)\cdot \cdot \cdot 1}$

이고, 위 식은 $1\leq i\leq p-1$일 때 $p$의 배수이므로 p로 나누면 없어지게 됩니다. 또한, $i$가 $0$ 또는 $p$이면 1입니다. 따라서,

$(k+1)^{p}\equiv \binom{p}{0}k^{0}+\binom{p}{p}k^{p} = k^{p}+1\equiv k+1($mod $p)$

$a=k+1$일 때도 성립함을 증명했습니다. 따라서,따라서, $a\geq 0$에 대하여 $a^{p}\equiv a($mod $p)$를 만족합니다.

$a$와 $p$가 서로소인 경우는 다음과 같이 유도할 수 있습니다.

$a^{p}\equiv a($mod $p)$이므로, $a^{p} - a = a(a^{p-1}-1)$은 $p$로 나누어 떨어집니다. 이때, $a$와 $p$가 서로소이므로 $a^{p-1}-1$은 $p$로 나누어 떨어집니다.

따라서, $a^{p - 1}\equiv 1($mod $p)$를 만족합니다.