이항 계수 (1) 썸네일형 리스트형 백준 11439 - 이항 계수 5 icpc.me/11439 $N, K, M \leq 4 \times 10^6$ 일 때 $\binom{N}{K} \mod M$ 을 구하는 문제이다. 이 문제는 이항 계수 4까지 풀어나가면서 배운 지식을 활용할 수 없다. N, K가 크기에 단순한 dp로 풀 수 없고 M이 소수라는 보장이 없기에 페르마의 소정리조차 사용할 수 없다. 그렇다면 이건 개인용 컴퓨터로는 풀 수 없는 문제일까? 물론 그렇지 않다. 이 글을 따라가 보자. 소수 추출하기 간단하게 작은 수의 이항 계수를 구해보자. $\binom{5}{4}$ 를 계산한다고 했을 때 $\frac{5!}{4!\times(5 - 4)!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{(4 \times 3 \times 2 \ti.. 이전 1 다음
