PS를 위한 수학 - 뤼카 정리(Lucas Theorem)

뤼카 정리

뤼카 정리는 이항계수를 구하는 정리이다.

이항 계수를 구하는 일반적인 방법들

우리가 흔히 이항계수를 구하는 방법은 다음과 같다.

$\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}$

이 방법은 $O(n^2)$ 의 시간복잡도를 갖는다.

두 번째는 팩토리얼과 모듈러 역원을 이용하는 방법이다.

$\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}$ 이기 때문에 $O(n)$으로 $n!$ 까지만 팩토리얼을 전처리 해두면 모듈러 역원을 이용해 $n! \cdot k!^{-1} \cdot (n-k)!^{-1} \pmod m$ 과 같이 구할 수 있다.

이 방법의 시간복잡도는 $O(n)$ 정도라고 볼 수 있다.

뤼카 정리의 이점

뤼카 정리는 다음과 같은 이항 계수를 빠른 시간복잡도로 구할 수 있다.

$\dbinom{n}{k} \pmod p, \quad p \in \text{소수}$

시간 복잡도는 전처리에 $O(p^2)$ 혹은 $O(p \log p)$ 이며 $\dbinom{n}{k}$의 값을 얻어오는데는 $O(n \log_p n)$ 정도가 걸린다.

따라서 BOJ 11402 - 이항 계수 4같은 문제를 해결할 수 있다.

이 문제를 보면 $N \le 10^{18}$ 이고 $M \le 2,000$ 에 $M$이 소수이기 때문에 뤼카 정리를 쓰라고 만든 문제이다.

공식

뤼카 정리의 공식은 다음과 같다.

$n$과 $k$를 $p$진수로 나타낸 꼴이 다음과 같을 때,

$$ \begin{aligned} n&=n_q \cdot p^q+n_{q-1} \cdot p^{q-1} + \cdots +n_0 \cdot p^0 \quad (0 \le n_i < p) \\ k&=k_q \cdot p^{q}+k_{q-1} \cdot p^{q-1} + \cdots + k_0 \cdot p^0 \quad (0 \le k_i < p) \end{aligned} $$

$$ \begin{aligned} \dbinom{n}{k} \equiv \prod _{i=0}^q \dbinom{n_i}{k_i} \pmod p \end{aligned} $$

구현

증명보다 구현을 먼저 살펴보자.

우선 $O(p^2)$에 $\dbinom{p}{p}$ 까지 전처리를 해둔다 하자.

ll n, k, p;  
cin >> n >> k >> p;  
  
vector<vector<int>> binom(p + 1, vector<int>(p + 1));  
  
for (int i = 0; i <= p; i++)  
   for (int j = 0; j <= i; j++)  
      binom[i][j] = !i || !j ? 1 : (binom[i - 1][j] + binom[i - 1][j - 1]) % p;

이제 $n, k$를 $0$이 아닐때까지 $p$로 나눠주며 $\dbinom{n ~ \% ~ p}{k ~ \% ~ p} \pmod p$를 정답에 곱해주면 된다.

ll ret = 1;  
while (n || k) {  
   ret = (ret * binom[n % p][k % p]) % p;  
   n /= p, k /= p;  
}  
  
cout << ret;

구현은 굉장히 간단하다.

BOJ 11402 - 이항 계수 4 를 푸는 전체 코드는 다음과 같다.

void solve() {  
   ll n, k, p;  
   cin >> n >> k >> p;  
  
   vector<vector<int>> binom(p + 1, vector<int>(p + 1));  
  
   for (int i = 0; i <= p; i++)  
      for (int j = 0; j <= i; j++)  
         binom[i][j] = !i || !j ? 1 : (binom[i - 1][j] + binom[i - 1][j - 1]) % p;  
  
   ll ret = 1;  
   while (n || k) {  
      ret = (ret * binom[n % p][k % p]) % p;  
      n /= p, k /= p;  
   }  
  
   cout << ret;  
}

증명

Lemma 1.

$$ (1+x)^{p^n}\equiv 1 + x^{p^n} \pmod p $$

증명

$\dbinom{p}{n}=\dfrac{p!}{n!(p-n)!}=\dfrac{p(p-1) \cdots (p-n+1)}{n(n-1) \cdots 2 \cdot 1}$

$p$는 소수이므로 $p \mid \dbinom{p}{n}$

분자 $p$가 분모에서 나눠질 수 없기 때문이다. $n \neq p \ \text{and}\ n \neq 0$ 임을 가정한다.

이항정리에 의해

$$ \begin{aligned} (1+x)^p&=\displaystyle \sum_{i=0}^{p} \dbinom{p}{i}x^i \\ &=\dbinom{p}{0}x^0+\dbinom{p}{1}x^1+ \cdots +\dbinom{p}{p}x^p \end{aligned} $$

양 끝을 제외한 중간의 항들이 항상 $p$로 나누어 떨어지기 때문에

$$ \begin{aligned} (1+x)^p \equiv 1+x^p \pmod p \end{aligned} $$

비슷하게 $(1+x)^{p^n}$과 $1+x^{p^n}$ 에 대해서도 다음과 같이 유도할 수 있다.

$$ \begin{aligned} \\ (1+x)^{p^n} \equiv 1 + x^{p^n} \pmod p \end{aligned} $$

$\square$

뤼카 정리

다음과 같은 꼴을 보자.

$$ \begin{aligned} n&=n_q \cdot p^q+n_{q-1} \cdot p^{q-1} + \cdots +n_0 \cdot p^0 \quad (0 \le n_i < p) \\ k&=k_q \cdot p^{q}+k_{q-1} \cdot p^{q-1} + \cdots + k_0 \cdot p^0 \quad (0 \le k_i < p) \end{aligned} $$

다음과 같은 이항정리 식을 고려한다.

$$ \begin{aligned} \displaystyle \sum_{k=0}^{n}\dbinom{n}{k}x^k&=(1+x)^n=(1+x)^{n_q \cdot p^q+n_{q-1} \cdot p^{q-1} + \cdots +n_0 \cdot p^0} \\ &=\prod_{i=0}^{q} \left[(1+x)^{p^i} \right]^{n_{i}} \end{aligned} $$

Lemma 1에 의해

$$ \begin{aligned} \prod_{i=0}^{q}\left[ (1+x)^{p^i} \right]^{n_{i}} &\equiv \prod_{i=0}^{q}\left[ 1+x^{p^i} \right]^{n_{i}} \\ &\equiv (1+x^{p^q})^{n_q}\cdot (1+x^{p^{q-1}})^{n_{q-1}} \cdots (1+x^{p^0})^{n_0} \pmod p \end{aligned} $$

위 식을 전개했을 때 차수가 $k$인 $x^k$가 되기 위해서 $x^{p^i} \quad (0 \le i \le q)$ 가 곱해진 횟수들을 고려한다.

이 각각의 횟수들을 $k_i\ \ (0 \le i \le m, ~ 0 \le k_i \le n_i)$ 라고할 때,

$k=k_q \cdot p^q+k_{q-1} \cdot p^{q-1} + \cdots + k_0 \cdot p^0$ 를 만족해야 한다.

차수가 $k$가 되기 위해서 $x^{p^q}$ 가 곱해지는 횟수를 $k_q$ 라고 할 때, 곱셈에서 차수의 결과는 차수끼리 더한것과 같기 때문에 위와 같은 식이 나왔다.

그럼 $x^k$의 계수는 $\displaystyle \prod_{i=0}^{k} \dbinom{n_i}{k_i}$ 가 되는데, 이항정리에 의해 $\left[ 1+x^{p^i} \right]^{n_i}=\displaystyle \sum_{j=0}^{n_i} \dbinom{n_i}{j}(x^{p^{i}})^{j} \cdot 1^{n_i-j}$ 의 꼴에서 $k_i$개를 고르는 조합의 가지수들을 모두 곱해주었기 때문이다.

결론적으로

$$ \begin{aligned} \displaystyle \prod_{i=0}^{q}\left[ 1+x^{p^i} \right]^{n_i} &\equiv (1+x^{p^q})^{n_q}\cdot (1+x^{p^{q-1}})^{n_{q-1}} \cdots (1+x^{p^0})^{n_0} \\ &\equiv \displaystyle \sum_{k=0}^{n} \prod_{i=0}^{q} \dbinom{n_i}{k_i}x^k \pmod p \end{aligned} $$

$x^k$의 계수를 고려했을 때 원래 이항계수에서 $\dbinom{n}{k}$ 이지만 법 $p$에 대해 새로운 꼴에선 $\displaystyle \prod_{i=0}^{q}\dbinom{n_i}{k_i}$ 꼴이 되었으므로

$$ \dbinom{n}{k}\equiv \prod_{i=0}^{q}\dbinom{n_i}{k_i} \pmod p \quad (0 \le n_i < p , 0 \le k_i \le n_i) $$

$\blacksquare$

---

참고