53. Lucas' Theorem

뤼카 정리(루카스 정리, Lucas' Theorem)는 이항계수 $_n\mathrm{C}_r$을 소수 $p$로 나눈 나머지를 구할 때 사용되는 정리이다. 이 정리를 이용하면 $n$과 $r$이 클 때에도 이항계수를 빠르게 구할 수 있다. 정리의 내용은 다음과 같다.

$$_n\mathrm{C}_r=(_{\lfloor n/p \rfloor}\mathrm{C}_{\lfloor r/p \rfloor})(_{n\,\bmod\,p}\mathrm{C}_{r\,\bmod\,p})\bmod p$$

만약 $n<r$인 경우 $_n\mathrm{C}_r = 0$으로 간주한다. $_0\mathrm{C}_0 = 1$이다.

위의 식을 다르게 해석하면, $n$과 $r$을 $p$진법으로 나타냈을 때 $i$번째 자리의 자리값을 각각 $n_i, r_i$라고 하면 $_n\mathrm{C}_r$을 $p$로 나눈 나머지는 모든 $_{n_i}\mathrm{C}_{r_i}$의 곱을 $p$로 나눈 나머지와 같다는 의미가 된다. 이 값이 $0$이 아니기 위해서는 $n_i<r_i$인 경우가 한 번도 나오지 않아야 한다.

 

이 방법을 이용하면 $p$가 크지 않은 경우 이항계수를 효과적으로 구할 수 있게 된다. $p$ 미만의 수에 대한 팩토리얼 값이 전처리되어 있을 경우 이항계수를 구하는 코드는 다음과 같다. 전처리는 이 글에 나온 대로 하면 된다.

typedef long long LL;
LL f(LL n, LL r, LL p)
{
    if(n < r)return 0;
    else if(n == r)return 1;
    else return f(n / p, r / p, p) * modinv(f[n], f[r] * f[n - r] % p) % p;
}

$p$가 $5000$ 이하로 작다면 처음부터 $2$차원 배열에 이항계수를 저장해서 $\text{modinv}$ 함수 없이 구현할 수도 있다.

 

[연습문제]

 

BOJ 11402. 이항 계수 4 (Platinum V)

뤼카 정리로 이항계수를 구하는 문제이다. $M \le 2000$이므로 $2$차원 배열을 이용할 수 있다.

 

→ solved.ac tag: lucas