BJ 14854 이항 계수 6 - (1)

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

이항 계수 시리즈 중에서는 가장 어려운 문제가 아닐까 생각됩니다.
제출 수도 많지 않고, 관련 블로그 글 뿐만 아니라 해외 문서에서도 이와 관련된 직접적인 내용을 찾을 수 없었습니다.

문제를 가장 어렵게 만드는 것은 아마 142857이 소인수분해 했을 때 3^3×11×13×37 로 분해되어, square-free가 아님이 문제를 어렵게 만들 것입니다.. 즉,

를 구하는 빠른 시간 내에 작동하는 알고리즘을 구상해야 하는데, 기존의 소인수분해를 기반으로 한 방법은 너무 느려 쿼리형 문제에는 사용할 수 없기 때문입니다.

어떻게 해결할 수 있을까요?

Andrew Granville의 논문

1997 나온 Andrew Granville의 논문에서 그 해답을 찾을 수 있습니다. 논문 링크
크게 어려운 영문적 해석은 들어있지 않고, 우리가 원하는 문제에 대한 답은 짧은 섹션에 담겨져 있어서 찬찬히 살펴보면 수월하게 읽을 수 있을 것입니다.

우리가 원하는 정보만을 파악해보겠습니다. 증명은 논문을 직접 읽어보시길 바랍니다.

+2021. 01. 16. 수정

아마 링크를 참조한 논문을 그대로 읽으면 문제가 발생할 것입니다. 논문의 내용에 일부 오류가 존재합니다. 이는 실제 출판본에서는 수정된 내용이나, 잘 알려져 있지 않습니다. 수정된 내용은 다음과 같습니다:

1. $m=n+r$이 아닌 $n=m+r$입니다.
2. 저자는 $e_j$를 $n_i<m_i$를 만족하는 $i\ge j$인 $i$의 개수, 즉 받아올림(carry)의 개수라고 서술하였으나, 실제 이 둘은 다릅니다. 정확한 정의는 $m$과 $r$을 $p$-진법으로 나타냈을 때의 받아올림의 개수입니다.
3. 그 밖에 $(\pm 1)^{e_{q-1}}$의 위치가 좌변으로 이동하는 등 가독성 측면에서의 수정이 이루어졌습니다.

이는 다음 글을 참조하였습니다. 출판된 논문은 여기서 볼 수 있습니다.

Definition 1

주어진 정수 $n$에 대해, $(n!)_p$을 다음과 같이 정의한다:

즉, $(n!)_p$는 $n$ 이하의 음이 아닌 정수 중 $p$의 배수가 아닌 것들의 곱이다.

Theorem 1

소수 $p$의 거듭제곱 $p^q$와 $n=m+r$을 만족하는 양의 정수 $n$이 주어졌을 때, $n$의 $p$-진 표기법에서 나타나는 자리수를 각각 $n_0,\ n_1,\ \ldots,\ n_d$라 하고, $N_j=\left\lfloor n/p^j\right\rfloor\pmod {p^q}$라 하자. 동일한 정의를 $m_j, M_j, r_j, R_j$에 대해서도 시행한다. 이제, $i\ge j$에 대해 $m_i$와 $r_i$를 더할 때 받아올림이 일어나는 첨자 $i$의 개수를 $e_j$라 했을 때, 다음이 성립한다.

또한, 복부호 $(\pm 1)$은

이고, ${N_j \choose M_j}_p=(N_j!)_p/(M_j!)_p(R_j!)_p$ 이다.

Theorem 2와 Theorem 3은 빠른 계산을 위한 추가적인 정리이지만, 우리가 얻어야 할 법 27에 적용할 수 없으므로 생략했습니다.

해석

이전의 Lucas Theorem에 비해 상당히 내용이 복잡하기 때문에, 그 예시로 ${16 \choose 5} \pmod {3^3}$에 대해 위 Theorem 1을 적용해 보도록 하겠습니다.

n_j, m_j, r_j 구하기

가장 먼저 해야 할 것은 $n=16$, $m=5$, 그리고 $r=16-5=11$에 대한 3-진 전개를 수행하는 것입니다.

이 때 주의해야 할 점은, 바로 문제에서 요구하는 $p^d$까지의 전개는 $d$가 적어도 $(q-1)$ 이상이여야 한다는 것입니다. 그렇지 않으면 나중에 $e_{q-1}$을 구할 수 없습니다.

N_j, M_j, R_j 구하기

두 번째로 해야 할 것은 $j=0,1,\ldots,d$에 대해 $N_j,\ M_j,\ R_j$를 구하는 것입니다. 알고리즘 상으로 $N_0=n \pmod {p^q}$를 구한 후 3으로 나눈 몫을 차례로 구해나가면 됩니다.

e_j 구하기

다음으로 $e_j$를 구해봅시다. $m_j$와 $r_j$를 더했을 때 받아올림을 계산해 볼까요?

따라서 $e_0=1$, $e_{q-1}=0$ 입니다.

(N_j!)_p, (M_j!)_p, (R_j!)_p 구하기

따라서

입니다.

계산 마무리

$p=3$이므로 복부호는 $(-1)$일 테고, $e_{q-1}=e_2=0$ 입니다.

따라서 문제의 답은 21입니다.

알고리즘 평가: 쓸만한가요?

이 알고리즘은 과연 문제에 적용하기에 괜찮은 방법일까요?

논문의 저자 Andrew Granville은 3. Fast computation of binomial coefficients (mod p^q)에서 Theorem 1을 적용하는 데 $O(\log^2 n)$의 시간복잡도가 필요하다고 밝혔습니다. 통상적으로 적용하는 1초당 1억번의 연산 중, 최대 10만개의 테스트 케이스를 생각하면 전처리/입출력 시간을 제외했을 때 회당 200번의 연산만으로 이를 해결해야 합니다. N의 최대 범위가 $10^9$까지이므로, 넉넉하진 않지만 고려해 볼 만 합니다.

문제는 Theorem 1을 적용하는 것이 $\frac 1 {p^k} {n \choose m }\pmod{p^q}$를 $a<p^q$인 $a$에 대해 $(a!)_p$의 곱으로 나타내는 단계까지를 의미합니다(논문에서는 이후 $(a!)_p$를 $O(q^4\log n \log p + q^4p \log^3 p)$ 시간에 계산하는 방법을 제시하고 있으나, 우리가 계산하는 경우에서는 $p=3$이므로 이 방법을 사용할 수 없습니다). $p^q=27$이므로 전처리 단계에서 이를 수행해도 짧은 시간이 걸리겠지만, 이를 나누는 과정에서도 시간이 소요될 것을 생각하면 가능할 지는 직접 실행해 보아야 알 것입니다.

무엇보다 법 27에 대한 나머지 말고도 법 11, 13, 37에 대한 나머지를 계산해야 하고 이를 중국인의 나머지 정리를 이용해 법 142857에 대한 답을 구해야 한다는 점에서, 정말 어려운 문제가 아닐수 없다고 말해야 할 것 같습니다.

코드 구현과 중국인의 나머지 정리를 이용한 최종 결과 출력은 다음 게시글에서 이어집니다.