문제 링크

<aside> 💡 조합론/다이나믹 프로그래밍/뤼카 정리/수학/정수론

</aside>

Memory 224880KB Time 516ms Code Length 935B

import sys
sys.setrecursionlimit(5000) 

def binomial(n, k, p):
    if cache[n][k] != 0:
        return cache[n][k]

    if k == 0 or n == k:
        cache[n][k] = 1
        return cache[n][k]

    cache[n][k] = (binomial(n-1, k-1, p) + binomial(n-1, k, p) % p)
    return cache[n][k]

def get_digits(n, b):
    d = []
    while n:
        d.append(n % b)
        n //= b
    return d

def lucas_theorem(n, k, p):
    ret = 1
    nd = get_digits(n, p)
    kd = get_digits(k, p)

    for i in range(max(len(nd), len(kd))):
        nn, kk = 0, 0
        if i < len(nd):
            nn = nd[i]
        else:
            nn = 0

        if i < len(kd):
            kk = kd[i]
        else:
            kk = 0

        if nn < kk: 
            return 0

        ret = (ret * binomial(nn, kk, p) % p) 

    return ret

n, k, m = map(int, input().split())
cache = [[0 for _ in range(2010)] for _ in range(2010)]

print(lucas_theorem(n, k, m))

이 코드는 루카스의 정리를 이용하여 이항 계수를 계산하는 프로그램이다. 먼저, 재귀 함수의 깊이 제한을 5000으로 설정한다. binomial 함수는 이항 계수를 계산하고, 이미 계산된 값을 캐시에 저장하여 재사용한다. get_digits 함수는 주어진 수를 특정 진법으로 변환하여 각 자릿수를 리스트로 반환한다.

루카스의 정리를 구현한 lucas_theorem 함수는 두 수의 각 자릿수를 p 진법으로 변환하고, 각 자릿수에 대해 이항 계수를 계산한다. 모든 자릿수에 대해 이를 수행하고, 그 결과를 모두 곱한다. 이 때, n의 i번째 자릿수가 k의 i번째 자릿수보다 작으면 0을 반환한다.

마지막으로, 사용자로부터 n, k, m을 입력받아 이를 lucas_theorem 함수에 전달하고, 결과를 출력한다. 이 때, m은 계산에 사용되는 진법을 나타낸다.