이항계수를 소수로 나눈 나머지 구하는 방법 - Lucas' Theorem 배우고 적용하기

https://en.wikipedia.org/wiki/Lucas%27s_theorem

Lucas's theorem - Wikipedia

 

1. Lucas' Theorem

 

정수 m,n과 소수 p에 대하여 $$\binom{m}{n} ≡ \prod_{i = 0}^{k} \binom{m_{i}}{n_{i}} (mod p)$$

 

여기서 $m_{i}$와 $n_{i}$는 m,n을 p진법 전개했을때 얻을 수 있는 수이다. 

 

구체적으로 $$m = m_{k}p^{k} + m_{k-1}p^{k-1} + ... + m_{1}p + m_{0}$$

 

$$n = n_{k}p^{k} + n_{k-1}p^{k-1} + ... + n_{1}p + n_{0}$$

 

 

2. 증명

 

https://en.wikipedia.org/wiki/Binomial_theorem

Binomial theorem - Wikipedia

 

이항정리로부터 다음 식을 얻는다.

 

$$(1+x)^{p} = \sum_{r = 0}^{p} \binom{p}{r}x^{r}$$

 

여기서, $$\binom{p}{r} = \frac{p*p-1*p-2...*1}{(p-r) * (p-r-1)...(1) * r*r-1*r-2*...*1}$$

 

즉, $r = 0,p$를 제외한 모든 r = 1,2,...,p-1에 대하여 $\binom{p}{r} (mod p) ≡ 0$

 

그래서, $$(1+x)^{p} ≡ 1+x^{p}$$

 

귀납법으로 음이 아닌 정수 i에 대하여 $$(1+x)^{p^{i}} ≡ 1+x^{p^{i}} (mod p)$$

 

https://artofproblemsolving.com/wiki/index.php/Lucas%27_Theorem

Art of Problem Solving

 

여기서 $(1+x^{p^{k}})^{p}$를 전개할때는 x를 $x^{p^{k}}$로 보고 이항전개를 한 것이다.

 

이제, m의 p진법 전개 $m = \sum_{i = 0}^{k}m_{i}p^{i}$에 대하여

 

$$\sum_{n = 0}^{m} \binom{m}{n}x^{n} ≡ (1+x)^{m} ≡ (1+x)^{m_{0}+m_{1}p+m_{2}p^{2}+...m_{k}p^{k}}$$

 

$(1+x)^{p^{i}} ≡ (1+x^{p^{i}})$를 이용하면 다음과 같다.

 

$$\prod_{i=0}^{k}(1+x)^{m_{i}p^{i}} ≡ \prod_{i = 0}^{k}(1+x^{p^{i}})^{m_{i}}$$

 

바로 위에서 제시한 이항전개 테크닉을 이용해서

 

$$(1+x^{p^{i}})^{m_{i}} = \sum_{n_{i} = 0}^{m_{i}}\binom{m_{i}}{n_{i}}x^{n_{i}p^{i}}$$

 

합의 기호와 곱의 기호는 서로 바꿀 수 있다. $f(m_{i}, n_{i}) = \binom{m_{i}}{n_{i}}x^{n_{i}p^{i}}$라고 해보자.

 

$$\prod_{i=0}^{k}\sum_{n_{i} = 0}^{m_{i}} f(m_{i}, n_{i}) = \prod_{i=0}^{k} (f(m_{i},0) + f(m_{i},1) + ... +f(m_{i},m_{i}))$$

 

$$(f(m_{0},0)+...+f(m_{0},m_{0}))(f(m_{1},0)+...+f(m_{1},m_{1}))...(f(m_{k},0)+...+f(m_{k},m_{k})) = \sum_{i_{j}}f(m_{0},i_{0})f(m_{1},i_{1})...f(m_{k},i_{k})$$

 

$$\sum_{i_{j}}\prod_{i=0}^{k}f(m_{i},n_{i}) = \sum_{i_{j}}(\prod_{i=0}^{k}\binom{m_{i}}{n_{i}})x^{\sum_{i=0}^{k}n_{i}p^{i}} = \sum_{n = 0}^{m}(\prod_{i=0}^{k}\binom{m_{i}}{n_{i}})x^{n}$$

 

여기서 $n = \sum_{i = 0}^{k}n_{i}p^{i}$으로 n에 대한 p진법 전개이다.

 

그러므로, $$\sum_{n = 0}^{m}\binom{m}{n}x^{n} ≡ \sum_{n = 0}^{m}\prod_{i=0}^{k}\binom{m_{i}}{n_{i}}x^{n} (mod p)$$ 은 x에 대한 항등식이다.

 

따라서, $x^{n}$의 계수 $$\binom{m}{n} ≡ \prod_{i = 0}^{k}\binom{m_{i}}{n_{i}} (mod p)$$

 

 

3. 연습문제

 

11402번: 이항 계수 4 (acmicpc.net)

11402번: 이항 계수 4

 

4. 풀이

 

m진법 전개를 하면 이항계수의 n,k가 m으로 나눈 나머지 0,1,...,m-1로 바뀌므로 factorial을 구하기 용이하다.

 

n,k가 매우 크고 m이 충분히 작은 이 문제와 같은 경우 뤼카의 정리가 유용하다.

 

즉 factorial로 필요한건 m으로 나눈 나머지인 0,1,2,...,m-1까지이다. 

 

이를 다이나믹 프로그래밍으로 미리 구해둔다. 

 

당연히 factorial을 m으로 나눈 나머지를 저장해두는 것이 조금이나마 유리하다.

 

n,k,m = map(int,input().split())

factorial = [0]*m
factorial[0] = 1

for i in range(1,m):
    
    factorial[i] = factorial[i-1] * i
    factorial[i] %= m

 

다음에 필요한건 n,k의 m진법 전개이다.

 

m진법 전개는 2진법으로 표현할때 2로 나눈 몫,나머지를 반복적으로 구하고 나머지만 모아서 쓰던걸 기억한다면...

 

m으로 나눈 몫, 나머지를 반복적으로 구하고 나머지만 챙기면 된다.

 

 

n을 m으로 나눈 몫이 n//m이고 n%m인데, n%m을 $n_{0}$라 하고.. n//m을 n으로 갱신해준다.

 

마찬가지로 k도 k//m을 k라 갱신하고 k%m을 $k_{0}$라 하고...

 

먼저 구한 $n_{0}$와 $k_{0}$에 대하여, $\binom{n_{0}}{k_{0}} mod m$을 구해준다.

 

m이 소수이고 $n_{0}$와 $k_{0}$가 m으로 나눈 나머지이므로 서로소여서 페르마의 소정리를 적용할 수 있다.

 

즉, $$\binom{n_{0}}{k_{0}} ≡ (n_{0})!((n_{0} - k_{0})!(k_{0})!)^{m-2} (mod m)$$

 

이를 반복해서 구하면 되는데... 언제까지 반복해야하는가?가 고민이다.

 

특히 n,k는 다른 수이니 m진법 전개를 하면 길이가 다를게 뻔하다..

 

그러니까 n이 더 크니까 $n_{i}$는 계속 나오는데 $k_{i}$는 어느순간 계속 0이 나올게 뻔하다..

 

그런데 이항계수의 성질 k = 0이면 $$\binom{n}{k} = 1$$ 이므로, 더 큰 수인 n이 0보다 클 때까지 반복하면 될 것이다.

 

그런데 또 하나 문제는 n이 더 크다고 해서 m으로 나눈 나머지인 $n_{i}$도 더 크다는 보장은 없다.

 

하지만 이항계수의 성질 n < k 이면 $$\binom{n}{k} = 0$$ 을 이용하면...

 

나누는 과정을 반복하다가.. $\binom{n_{i}}{k_{i}} (mod m)$을 answer에 곱해나가는데...

 

$\binom{n_{i}}{k_{i}} = 0$을 곱하면... answer은 무조건 0이 될 것이므로... $n_{i} < k_{i}$이면 answer = 0으로 하고 반복문을 종료한다.

 

#lucas theorem
n,k,m = map(int,input().split())

factorial = [0]*m
factorial[0] = 1

#m으로 나눈 나머지인 0,1,..,m-1!을 구해준다.
for i in range(1,m):
    
    factorial[i] = factorial[i-1] * i
    factorial[i] %= m

answer = 1

#n > 0일때까지 반복해나감
while n > 0:
    
    n,r1 = n//m, n%m
    k,r2 = k//m, k%m
    
    #n,k를 m으로 나눈 나머지인 r1,r2에 대해 r1Cr2 mod m을 구해준다.
    #m은 소수이고 r1,r2는 m과 서로소이므로 페르마의 소정리를 이용
    #그런데, r1 < r2이면 r1Cr2 = 0이므로 바로 반복문을 종료
    if r1 >= r2:
        
        answer *= (factorial[r1])*pow(factorial[r1-r2]*factorial[r2],m-2,m)
        answer %= m
    
    else:
        
        answer = 0
        break


print(answer)