BJ 14854 이항 계수 6 - (1)

이경헌·2021년 1월 13일

백준 - 이항 계수

목록 보기

7/8

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

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

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

{n \choose m} \pmod {p^q}

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

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

Andrew Granville의 논문

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

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

+2021. 01. 16. 수정

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

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

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

Definition 1

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

(n!)_p=\prod_{1\le k\le n,\ p\nmid k}^n k

즉, $(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$ 라 했을 때, 다음이 성립한다.

\frac {(\pm 1)^{e_{q-1}}} {p^{e_0}} {n \choose m} \equiv \prod_{j=0}^d {N_j \choose M_j}_p \pmod {p^q}

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

(\pm 1)=\begin{cases} 1 & \text{if } p=2\text{ and } q\ge 3 \\ -1 & \text{otherwise} \end{cases}

이고, ${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-진 전개를 수행하는 것입니다.

\begin{aligned} 16&=121_{(3)}=1\times 3^0+2\times 3^1+1\times 3^2 \rightarrow (n_0,n_1,n_2)=(1,2,1) \\ 5 &=012_{(3)}=2\times 3^0+1\times 3^1+0\times 3^2 \rightarrow (m_0,m_1,m_2)=(2,1,0)\\ 11&=102_{(3)}=2\times 3^0+0\times 3^1+1\times 3^2 \rightarrow (r_0,r_1,r_2)=(2,0,1) \end{aligned}

이 때 주의해야 할 점은, 바로 문제에서 요구하는 $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으로 나눈 몫을 차례로 구해나가면 됩니다.

\begin{aligned} (N_0,N_1,N_2)&=(16,5,1) \\ (M_0,M_1,M_2)&=(5,1,0) \\ (R_0,R_1,R_2)&=(11,3,1) \end{aligned}

e_j 구하기

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

$j$	0	1	2
$m_j$	2	1	0
$r_j$	2	0	1
carry	Yes	No	No
$e_j$	1	0	0

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

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

(N_0!)={16!\over 5!\times 3^5},\ (M_0!)={5! \over 3},\ (R_0!)={11! \over 3!\times 3^3}, \\[10pt] (N_1!)={5! \over 3},\ (M_1!)=1!,\ (R_1!)={3! \over 3}, \\[10pt] (N_2!)=1!,\ (M_2!)=0!, (R_2!)=1!

따라서

{N_0\choose M_0}_p=\frac{364}{5},\ {N_1\choose M_1}_p=20,\ {N_2\choose M_2}_p=1

입니다.

계산 마무리

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

\frac 1 3 {16\choose 5}\equiv (-1)^0\times \frac{364}{5}\times 20\times 1\equiv 25 \pmod{3^3} \\ {16\choose 5}\equiv 21 \pmod{3^3}

따라서 문제의 답은 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에 대한 답을 구해야 한다는 점에서, 정말 어려운 문제가 아닐수 없다고 말해야 할 것 같습니다.

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

이경헌

Undergraduate student in Korea University. Major in electrical engineering and computer science.