[ 알고리즘 ] 뤼카의 정리 (Lucas' theorem)

뤼카의 정리 (Lucas' theorem)는 다음과 같이 정리할 수 있습니다.

 

$_{n}\textrm{C}_{r}$을 $m$으로 나눈 나머지를 구하고자 할 때 사용할 수 있습니다.

 

$\binom{n}{r} = \prod_{i=1}^{k}\binom{n_{i}}{r_{i}}\; mod\; p$

 

1. $_{n}\textrm{C}_{r}$의 $n$과 $r$을 각각 $m$진수로 표현합니다.

 

2. $m$진수로 표현된 두 수를 각 자릿수에 맞춰 조합을 계산하고, 그 값들을 모두 곱해 $m$으로 나눈 나머지 값이 최종값입니다.

 

3. 이때, $n < r$이면 값은 0입니다.