[백준 11402] 이항 계수 4(python)

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

11402번: 이항 계수 4

이항 계수 4 문제

이항 계수를 소수로 나누었을 때의 나머지를 구하는 문제

뤼카의 정리를 이용하여 해결할 수 있다.

⚙️정답 코드

def Lucas(n,k): #뤼카의 정리
    if n < k : # nCk 에서 K가 더 클 경우
        return 0
    elif n == k : # nCk 에서 n과 k가 같을 경우
        return 1 
    x = 1
    for i in range(1, k+1): # 그외 k가 더 큰 경우 k까지 늘려가면서 
        x *= n - i + 1 # 곱해주고
        x //= i # 나눠주자
    return x
        

import sys
N, K, M = map(int, sys.stdin.readline().split())
n, m = [], []
cnt = 0
while N or K : # 둘중 0이 될 때 까지
    n.append(N%M) #소수로 나눈 나머지 기록
    m.append(K%M) #소수로 나눈 나머지 기록
    N //= M
    K //= M
    
result = 1
for i in range(len(n)):
    result *= Lucas(n[i],m[i]) #뤼카의 정리를 이용한 계산
    result %= M
print(result)

📌문제 접근 포인트

1. 문제의 요구 조건은 이항계수(조합)를 소수인 M으로 나누었을 때의 나머지를 구하는 문제이다.
2. 뤼카의 정리는 아래와 같은 식이 성립하는 것을 의미하는데 사실 단순히 이거만 봐서는 이해하기 어렵다.

이것의 예시는 다음과 같은 방법으로 풀이할 수 있다.
n = 1222, k = 322, p = 7이라고 하면 n과 k를 다음과 같은 꼴로 만들어 준다.
n = 4*7^3 + 6*7^2 + 3*7*1 + 3*7^0
k = 0*7^3 + 4*7^2 * 6*7^1 + 3*7^0
즉 각각의 자리에 해당하는 [4,6,3,3], [0,4,6,3]을 이용해서 아래와 같은 형태로 만들어 줄 수 있다.
1222C322 = (4C0 * 6C4 * 3C6 * 3C3) mod 7
따라서 0의 답을 얻을 수 있게 되는 과정을 의미한다.
3. 이 과정을 코드로 동일하게 구현해서 각 부분을 구해주면 어렵지 않게 답을 찾을 수 있다.