사용자 도구

사이트 도구


ps:problems:boj:11402

이항 계수 4

ps
링크acmicpc.net/…
출처BOJ
문제 번호11402
문제명이항 계수 4
레벨플래티넘 5
분류

수학, 정수론

시간복잡도O(m + logn/logm)
인풋사이즈n<=10^18, m<=2000
사용한 언어Python
제출기록28776KB / 64ms
최고기록56ms
해결날짜2021/01/20

풀이

  • 모듈러스가 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()

토론

댓글을 입력하세요:
P Z G R X
 
ps/problems/boj/11402.txt · 마지막으로 수정됨: 2021/01/31 17:18 저자 teferi