이항계수 \(\begin{pmatrix}N\\K\end{pmatrix}\)를 1,000,000,007(이하 P)로 나눈 나머지를 빠르게 구하는 문제입니다. 이항 계수는 \(\begin{pmatrix}N\\K\end{pmatrix}=\frac{N(N-1)(N-2)...(N-K+1)}{K(K-1)(K-2)...1}\)로 쓸 수 있는데, 여기서 중요한 것은 문제에서 요구하는 것이 저 값이 아니라 나머지값을 요구한다는 것입니다. 따라서 일반 나눗셈이 아닌 나머지 집합에서의 나눗셈(곱셈의 역연산)을 진행해야 합니다. 위 식의 분수꼴 대로, N에서 (N-K+1)까지의 곱과 K!을 구한 후 앞의 곱에서 나눗셈의 연산자로로 K!을 집어넣는 것이죠.
이제 나머지에서의 나눗셈에 대해 생각해보겠습니다. 이 나눗셈은 곱셈의 역원을 구하는 과정입니다. n과 서로소인 정수 a에 대해 \(ab\equiv 1\pmod{n}\)인 b를 찾는 과정이죠. 이 b를 찾을 때 1부터 n까지 모두 대입해보면서 찾는 것은 비효율적입니다. 문제에서 사용하는 n은 1,000,000,007로 소수입니다. 이것을 이용하면 보다 빠르게 역원을 구할 수 있을 것입니다. 페르마의 소정리를 응용해서 말이죠. 페르마의 소정리는 소수 p와 정수 a에 대해 \(a^{p-1}\equiv 1\pmod{p}\)를 만족한다는 정리입니다. 조금 다르게 써보면 \(a\times a^{p-2}\equiv 1\pmod{p}\)이 되고, 위의 곱셈의 역원을 구하는 과정을 생각해보면 ap-2가 a의 곱셈에 대한 역원입니다. 즉, 우리가 해야 하는 것은 K!을 구하고, K!의 1,000,000,005승(p=1,000,000,007일 때 K!의 곱셈에 대한 역원)을 구해서 N에서 (N-K+1)까지의 곱에 곱해주는 것입니다. 이를 구해서 출력하면 됩니다.
*여기서 유의해야 하는 점은 위에서 언급한 모든 곱셈은 일반적인 정수의 곱셈이 아니라 나머지 집합 위에서의 곱셈입니다. 따라서 곱을 구한다는 것은 매 곱셈 연산마다 나머지 연산을 통해 값의 범위가 0에서 P 안에 속하도록 만들어야 합니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| C++ | 코드(Github) / 코드(백준) | 2020-04-04 01:41:17 |