조합론에서 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진
크기의 (순서 없는) 조합의 가짓수이다.
https://www.acmicpc.net/problem/11401
11401번: 이항 계수 3
자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
www.acmicpc.net
위 문제와 같이 nCr을 구함에 있어서, n과r이 크기가 매우 큰 경우에는 모듈 연산과 페르마의 소과 거듭 제곱의 분할 정복을 통하여 구할 수가 있다.
( 알고리즘 문제에서 대부분의 경우, 데이터가 매우 큰 경우에 반드시 모듈 연산을 시킨다. 고로, 합동식의 성질과 거듭 제곱의 분할 정복을 까먹지 말자!!)
'알고리즘(アルゴリズム） > 자주 까먹는 알고리즘(よく忘れるアルゴリズム）' 카테고리의 다른 글
| 다익스트라 알고리즘 (0) | 2023.06.15 |
|---|---|
| 이진수를 이용하여 O(log n)으로 거듭 제곱 빠르게 계산하기 (2) | 2023.01.30 |
| Quad Tree - 2D 공간을 트리로 표현 (0) | 2023.01.26 |
| Stack과 Queue에 대한 고찰!!! (0) | 2023.01.26 |
| C++ - 2개 이상의 Delimiter를 사용한 Parsing Template (0) | 2023.01.24 |