이항 계수 4

• 모듈러스가 n보다 작은 소수일 경우의 이항 계수를 구하는 문제. 뤼카의 정리를 이용해서 푼다.
• 자세한 풀이는 이항 계수 - 모듈러스가 n보다 작은 소수일 때를 참고.
• 위의 링크에도 언급되어 있지만, C(n_i, k_i)를 계산하는 함수가, n_i < k_i 인 경우를 처리하는지 주의 할 것.

from teflib import combinatorics


def main():
    N, K, M = [int(x) for x in input().split()]
    comb_table = combinatorics.CombTable(M - 1, M)
    answer = 1
    while N > 0:
        N, n_mod = divmod(N, M)
        K, k_mod = divmod(K, M)
        answer *= comb_table.get(n_mod, k_mod)

    print(answer % M)


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.CombTable