페르마의 소정리 썸네일형 리스트형 이항계수를 구하는 알고리즘 이항계수 는 으로 정의되며 흔히 조합으로 알려져 있습니다. n개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수를 이항계수라고 합니다. 우리는 이항계수가 가지는 이라는 성질을 이용하여 메모제이션 해주어 O(N^2)의 시간과 메모리 복잡도를 가지는 전처리 한번으로 매 쿼리를 O(1)에 처리해줄 수 있습니다. 하지만 BOJ)11401 이항 계수 3 처럼 N이 큰 쿼리가 들어올 경우 O(N^2)의 방법으로는 해결할 수 없습니다. 그래서 개선된 방법을 필요로 합니다. 이는 맨 위에 정의 된 를 이용하는 방법입니다. 문제 조건에서 모듈러를 위한 소수가 주어질텐데 을 소수에 대한 의 역원을 구해주는 문제로 수정하여 해결하는 문제입니다. 우리는 동적 프로그래밍을 이용하여 n!을 계산하는데 O(N).. 더보기 이전 1 다음