Processing math: 100%

본문 바로가기

combinatorics

(2)

53. Lucas' Theorem 뤼카 정리(루카스 정리, Lucas' Theorem)는 이항계수

$_n\mathrm{C}_r$ 을 소수

$p$ 로 나눈 나머지를 구할 때 사용되는 정리이다. 이 정리를 이용하면

$n$ 과

$r$ 이 클 때에도 이항계수를 빠르게 구할 수 있다. 정리의 내용은 다음과 같다.

$_n\mathrm{C}_r=(_{\lfloor n/p \rfloor}\mathrm{C}_{\lfloor r/p \rfloor})(_{n\,\bmod\,p}\mathrm{C}_{r\,\bmod\,p})\bmod p$ 만약

$n위의 식을 다르게 해석하면,$ n

$과$ r

$을$ p

$진법으로 나타냈을 때$ i

$번째 자리의 자리값을 각각$ n_i, r_i

$라고 하면$ _n\mathrm{C}_r

$을$ p

$로 나눈 나머지는 모든$ _{n_i}\mathrm{..

46. Combinatorics 조합론(Combinatorics)은 순열과 조합, 경우의 수 등을 다루는 분야이다. 조합론 문제를 풀기 위해서는 약간의 배경지식이 필요하다. 팩토리얼(계승, Factorial)은

$0$ 이상의 정수에 대해 정의되는 함수로

$0! = 1, \color{#0000FF}{n!} = (n-1)! \times n$ 이다. 팩토리얼을 실수 범위로 확장한 감마 함수(Gamma Function)라는 것도 존재하지만 웬만한 알고리즘 문제를 풀기 위해서는 팩토리얼만 알고 있어도 괜찮다. 순열(Permutation): 서로 다른

$n$ 개의 원소 중

$r$ 개를 중복 없이 골라서 순서대로 나열하는 경우의 수를

$\color{#0000FF}{_n\mathrm{P}_r}$ 또는 $\color{#0000FF}{\mathrm{P}(n,..

티스토리툴바