BJ 11042 이항 계수 4

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

Lucas Theorem

뤼카의 정리는 어떤 이항 계수를 소수 $p$로 나눈 나머지를 구할 때 유용하게 쓸 수 있는 방법입니다.

임의의 음이 아닌 정수 $n$과 $k$, 그리고 소수 $p$에 대해 다음이 성립합니다.

이 때 $n_i$와 $k_i$는 각각 $n$과 $k$의 $p$-진 전개에서의 자리수입니다. 즉,

입니다.

접근 방법

10^18 까지의 큰 수이니 $O(\log n)$의 방법을 사용하는 것이 마땅할 것 같습니다. 주어진 n과 k를 각각 m진 전개하는데 소요되는 시간은 약 $\log_m{n}$, $\log_m{k}$입니다. 이들을 곱하는 것은 바로 수행 가능합니다. 이제 각 $n_i$와 $k_i$에 대해 이들의 이항 계수를 구하는 방법인데, 이전 글에서의 방법을 이용해 $O(\log n)$의 시간복잡도로 계산할 수 있습니다.

코드

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

def pow(n, k, m):
    if k == 1:
        return n
    pow_half = pow(n, k//2, m)
    if k % 2 == 0:
        return (pow_half ** 2) % m
    else:
        return (pow_half ** 2 * n) % m

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

def inverse(n):
    return pow(factorial[n], m-2, m)

mult = 1
while n != 0 or k != 0:
    n_digit = n % m
    n //= m
    k_digit = k % m
    k //= m

    if n_digit < k_digit:
        mult = 0
        break
    else:
        mult *= factorial[n_digit] * inverse(n_digit - k_digit) * inverse(k_digit)
        mult %= m

print(mult)