[BOJ][Python] 백준 19124번 - Binomial Coefficient
문제 링크: https://www.acmicpc.net/problem/19124
문제 풀이
정수론
설명은 정말 간단한 문제. ${}_{n}C_{k} \bmod 2^{32}$를 구하면 된다.
$2^{32}$는 매우 큰 수이기도 하고, 합성수여서 뤼카 정리를 사용하기에도 빡세보인다. 먼저 가장 쉬운 판별을 해보자.
${}_{n}C_{k} = 2^E \cdot U$로 나타낼 때 $E \geq 32$이면 나누어떨어지므로 $U$를 계산할 필요가 없어진다. 이 $E$를 구하는 방법이라면 Legendre's formula를 이용해도 좋고 어렵지 않다. 다만 $p = 2$의 경우에는 $\nu_{2}(n!) = n - s_2(n)$($n$을 이진수로 나타내었을 때 $1$의 개수)로도 나타낼 수 있으니, $\nu_{2}({}_{n}C_{k})$는 $n-s_2(n)-k+s_2(k)-(n-k)+s_2(n-k)$이므로, $s_2(k)+s_2(n-k)-s_2(n)$로도 구하는 것이 가능하다.
구했다면 $32$ 이상인지 확인하여, $0$을 출력할 지 결정하자. 만약 $32$ 미만이라면 이때부터 머리가 아파진다.
$p$를 $2^{32-E}$로 나눈 몫, $q$를 $2^{32-E}$로 나눈 나머지라고 하면 $U = p \cdot 2^{32-E} + q$가 된다. $U$ 값을 원래 식에 넣으면 $((p \cdot 2^{32-E} + q) \cdot 2^E)$이므로 $ p \cdot 2^{32} + q \cdot 2^E$가 된다. 이 식에 $ \bmod 2^{32}$를 하면 이제 $(q \cdot 2^{E}) \bmod {2^{32}}$가 되므로 $((U \bmod {2^{32-E}}) \cdot 2^E) \bmod {2^{32}}$를 구해주면 된다. 이렇게 되면 $U$에 대한 값을 조금 더 작은 값으로 구할 수 있게 된다.
한편으로 우리가 이 $U$ 값을 구해야 하는 이유는 $2$를 모두 걸렀기 때문에 역원 연산이 가능하다는 점이다. 그러면 $m!$을 다음과 같이 생각해보자.
$$m! = \left(\prod_{i=1, \text{ odd}}^m i\right) \cdot \left(\prod_{i=1, \text{ even}}^m i\right) = \left(\prod_{i=1, \text{ odd}}^m i\right) \cdot 2^{\lfloor \frac{m}{2} \rfloor} \cdot (\lfloor \frac{m}{2} \rfloor)! $$
이런 식으로 $m!$을 재귀적으로 구할 수 있다. 여기서 우리가 생각해보아야 할 점은 이 $U$ 값은 현재 $2$가 곱해져있지 않다는 점이다. 그러면 $2$를 뺀 값은 저 식보다 간단해질 거 같지 않은가?
$m!_{(2)}$를 $m!$에서 $2$의 거듭제곱을 모두 제거한 값이라고 정의하자. 위의 식을 이용하여 $m!_{(2)}$을 다음과 같은 식으로 바꿀 수 있다.
$$ m!_{(2)} = \left(\prod_{i=1, \text{ odd}}^m i\right) \cdot (\lfloor \frac{m}{2} \rfloor)! $$
$U$ 값은 $\frac{n!_{(2)}}{k!_{(2)}(n-k)!_{(2)}}$가 된다. 이제 $m!_{(2)}$만 구할 줄 알면 분수 꼴로 되어진 값을 우리는 모듈러 역원을 통해 구할 수 있게 되었다!
$(\frac{n!_{(2)}}{k!_{(2)}(n-k)!_{(2)}}) \bmod {2^{32-E}}$을 구하기 위해 위의 식을 토대로 재귀적으로 계산해야 한다. 여기서 $\prod_{i=1, \text{ odd}}^{2^{16}-1} (i + 2^{16} \cdot N) (N=0, 1, 2, \cdots) \bmod {2^{32}}$는 항상 일정한 값을 가지므로 계산을 압축할 수 있다. 분할 정복을 이용한 거듭제곱으로 구간 곱을 빠르게 계산해주고, 나머지는 나이브하게 곱해져도 반복 개수가 그렇게 크지 않으므로 빠르게 구할 수 있다. $n!_{(2)}$, $(k!_{(2)})^{-1}$와 $((n-k)!_{(2)}) ^ {-1}$를 구했다면, $U \bmod 2^{32-E}$를 구한 후 최종적으로 값을 구해주자.
코드