[수학] 조합을 구하는 다양한 방법들 - (3)

이번 시간에는...

---

이번 시간에는 본 시리즈를 시작하게 된 계기가 된 뤼카의 정리를 한번 살펴보고자 한다. 시작하기에 앞서, 이 정리는 아래 링크를 기반으로 내가 이해한 내용을 덧붙여 작성했음을 밝혀 둔다. 틀린 부분, 내가 잘못 이해한 부분 혹은 논리적 비약이 생기는 부분이 있을 수 있으니 의문점이 생긴다면 댓글로 알려주면 매우매우매우 감사하겠다!

 

https://ko.wikipedia.org/wiki/%EB%A4%BC%EC%B9%B4%EC%9D%98_%EC%A0%95%EB%A6%AC

뤼카의 정리 - 위키백과, 우리 모두의 백과사전

 

 

뤼카의 정리

---

뤼카의 정리는 다음과 같이 정의된다.

출처 : 위키피디아

 

C(m, n) 의 m, n값은 더 작은 값인 mi, ni를 이용한 C(mi, ni) 값의 곱과 p 모듈러 합동이다. 즉 작은 값들의 조합을 통해서 전체해를 빠르게 구할 수 있다는 강력한 기능을 보장한다. 이 mi, ni는 다음과 같이 구해진다.

 

출처 : 위키피디아

 

즉 mi, ni 역시 p와의 모듈러 연산을 통해 구할 수 있다. 이때 k값은 임의로 정할 수 있으며, mi, ni는 0과 같거나 크다. 즉 한쪽 값이 0이 되더라도 계속 전개 가능하다.

 

정리 증명

---

 

1. 다항식 증명 (Lemma 1)

 

우선 다음 식을 살펴보자.

 

 

위 식을 풀어쓰면, 다음과 같이 전개된다.

 

자, C(p, 0) = C(p, p) = 1이고, C(p, 1)부터 C(p, p-1)까지의 값은 모두 p를 인수로 가짐을 알 수 있다. 여기서 p-모듈러 연산을 적용하면 초항과 마지막 항을 제외한 모든 항이 제거된다. 즉

 

가 성립한다.

 

여기서 p의 m제곱 역시 귀납적으로 정의될 수 있으므로

 

가 성립한다.

 

2. 뤼카의 정리

 

이제 본격적으로 이항계수(조합) C(n, m)에 접근해보자. 위 식은 다음과 같이 변형될 수 있다.

 

또한 우리는 p-모듈러 연산을 통해 m, n을 다음과 같이 나타낼 수 있음을 앞서 살펴본 바 있다.

출처 : 위키피디아

 

즉 위 식을 변형하면...

 

또한, 위 Lemma 1에 의하여

 

가 성립한다.

우리는 n에 대해서도 m과 같이 p에 관하여 풀이해볼 수 있다. 즉 x^n의 차수에 대해, 이는 다음과 같이 나타난다.

이제 우변을 보자. 우변 역시 제곱 꼴을 이항계수의 합으로 나타낼 수 있다. 여기에서 우리는 x^(p^i * n_i)를 나타내는 계수는 C(m_i, n_i)임을 알 수 있다. 여기가 핵심이다.

 

즉 위 식을 변형하면 

 

 

이 된다. 우리는 이미 맨 첫번째 수식을 통해 x^n에 대한 계수가 C(m, n)임을 알고 있다. 또한 모든 n에 대해 이 수식이 p 모듈러 상에서 성립한다. 따라서

 

출처 : 위키피디아

 

실제 적용

---

이제 이 문제를 바로 ps문제에 적용해보자.

 

https://www.acmicpc.net/problem/11402

11402번: 이항 계수 4

 

이 식의 경우 이항 계수를 이루는 값이 매우 큰 상황으로, 기존의 방식을 적용하기에 어려움이 따른다. 이제 뤼카의 정리를 적용해서 풀어보자.

 

• n0, m0은 n, m을 p로 나눴을 때의 나머지값이다. 즉 C(m0, n0)은 C(m % p, n % p)과 동일하다.
• n_i, m_i는 n, m을 p로 i-1번 나눈 몫을 나눴을 때의 나머지값이 될것이다.
• 즉 n_i, m_i 모두 0이 될 때까지(이 이후값은 모두 0이 될 것이므로) 위 과정을 반복하면 된다.

while N or K :
  ans = (ans * math.comb(N % M, K % M)) % M 
  N //= M
  K //= M

 

여기서 combination 역시 생각해 볼 점이 있는데, 모든 n_i, m_i는 소수 p값 미만의 음이 아닌 정수이다(p 모듈러로 구해지므로). 본 문제는 단 한번의 조합값을 구하므로 math 라이브러리의 comb를 사용하였지만, 여러 케이스를 처리할 때는 DP 등으로 최적화할 수 있겠다. 가능한 경우의 수는 p^2, 전처리 과정에 최대 O(p^2)가 소요됨을 알 수 있다. 전체 풀이 코드는 다음과 같다.

 

import math

N, K, M = map(int, input().split())
ans = 1
while N or K :
  ans = (ans * math.comb(N % M, K % M)) % M 
  N //= M
  K //= M
print(ans % M)