직장인의 개발 일기

뤼카의 정리 (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입니다.