Processing math: 100%

본문 바로가기

lucas theorem

PS를 위한 정수론 - (4) 이항 계수 (nCr mod P) 구하는 다양한 방법 이항 계수

$_{n}C_r$ 을 소수

$p$ 로 나눈 나머지를 빠르게 구하는 다양한 방법들을 알아보자. 기본적으로 특정

$n$ 과

$r$ 에 대해서 이항 계수

$_{n}C_r$ 을 구하는 시간은

$O(1)$ 이 되어야 할 때, 즉, 많은 쿼리가 들어와도 문제가 없는 경우를 고려한다. 지금부터 소개하는 방법들의 시간복잡도는 전처리하는데 필요한 시간을 의미한다. 너무 작은

$n$ 과

$r$ 에 대해서 직접 분자와 분모를 모두 곱하는 경우는 생략한다. 1.

$O(n^2)$ www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에

$N$ 과

$K$ 가 주어진다. (1 ≤

$N$ ≤ 1,000, 0 ≤

$K$ ≤

$N$ ) www.acmicpc.net 파스칼의 삼각형을 이용하는 ..

티스토리툴바