https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98
이항 계수 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 이항 계수의 표를 파스칼의 삼각형이라고 한다. 조합론에서 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며
ko.wikipedia.org
\[
\binom{n}{k} =
\begin{cases}
\frac{n!}{k!(n-k)!} & \text{if } 0 \leq k \leq n \\
0 & \text{if } k < 0 \\
0 & \text{if } k > n
\end{cases}=
{n \mathrm{C} k}= C(n, k)
\]
\[
(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k}y^k = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}
\]
이항 계수는 조합론에서 중요한 역할을 하는 수학적 개념입니다. 어떤 정수 $n$과 $ k $ 에 대해, $ n $ 개의 다른 원소에서 $ k $ 개를 선택하는 방법의 수를 나타냅니다. 이항 계수는 $ \binom{n}{k} $ 또는 $ nCk $ 로 표기하며, 다음 공식으로 계산할 수 있습니다:
\[\binom{n}{k} = \frac{n!}{k!(n-k)!}\]
여기서 $ ! $는 팩토리얼을 나타내고, $ n! $ 은 1부터 $ n $ 까지의 모든 정수의 곱을 의미합니다.
알고리즘적 관점에서의 이항계수
이항 계수를 계산하는 여러 가지 방법이 있으며, 그 중 가장 간단한 방법은 직접 계산하는 것입니다. 하지만 이 방법은 $n$ 이나 $ k $ 의 값이 클 때 숫자가 매우 커지므로, 오버플로우를 일으키거나 비효율적일 수 있습니다.
재귀를 사용하는 방법:
이항 계수의 성질 $ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $ 을 이용하여 재귀적으로 계산할 수 있습니다. 이 방법은 간단하지만, 많은 중복 계산이 있어서 비효율적일 수 있습니다.
동적 계획법:
동적 계획법을 사용하여 이전에 계산한 값을 저장하고 재사용함으로써 중복 계산을 피할 수 있습니다. 이 방법은 시간 복잡도를 $ O(nk) $ 로 줄일 수 있으며, 공간 복잡도도 최적화할 수 있습니다.
파스칼의 삼각형:
파스칼의 삼각형을 이용하면 이항 계수를 계산할 수 있습니다. 이 삼각형의 각 숫자는 위의 두 숫자의 합으로 이루어지며, 이를 통해 $ \binom{n}{k} $ 의 값을 찾을 수 있습니다.
반복을 사용하는 방법:
반복적인 방법으로 이항 계수를 계산하는 것도 가능합니다. $\binom{n}{k}$의 값을 구할 때, $k$가 $n/2$보다 클 경우 $ \binom{n}{n-k}$를 계산하는 것이 더 효율적입니다.
루카스의 정리
루카스의 정리는 모듈로 소수 $p$에 대한 이항 계수를 계산할 때 유용합니다. 이 정리는 1878년에 에두아르 루카스(Édouard Lucas)에 의해 발표되었으며, 다음과 같이 정의됩니다:
정수 $n$과 $k$가 있고, 이들을 $p$진법으로 표현했을 때, $n = n_m p^m + n_{m-1} p^{m-1} + \ldots + n_0$ 그리고 $k = k_m p^m + k_{m-1} p^{m-1} + \ldots + k_0$ 라고 할 때,
\[ \binom{n}{k} \equiv \prod_{i=0}^{m} \binom{n_i}{k_i} \pmod{p} \]
여기서 $n_i$와 $k_i$는 $n$과 $k$의 $p$진법에서의 각 자릿수이며, $ \binom{n_i}{k_i}$는 $k_i$가 $n_i$보다 크면 0으로 정의됩니다.
루카스의 정리는 소수 모듈로 이항 계수를 효율적으로 계산할 수 있게 해줍니다.
중국인의 나머지 정리 (CRT: Chinese Remainder Theorem)
중국인의 나머지 정리는 여러 개의 서로소인 모듈로에 대한 연립 합동 방정식의 해를 찾는 데 사용됩니다. CRT는 다음과 같이 정의됩니다:
서로 다른 $n$개의 자연수$m_1, m_2, \ldots, m_n$이 주어졌을 때, 이들의 최소공배수는 $M = m_1 m_2 \ldots m_n$ 이고, 임의의 정수 $a_1, a_2, \ldots, a_n$에 대해, 연립 합동 방정식
\[ x \equiv a_1 \pmod{m_1}\]
\[x \equiv a_2 \pmod{m_2}\]
\[\vdots\]
\[x \equiv a_n \pmod{m_n} \]
은 $M$을 모듈로 했을 때 유일한 해 $x$를 가집니다.
CRT는 암호학에서 매우 중요한 역할을 하며, 큰 수를 다루는 알고리즘에서 효율성을 높이는 데 사용됩니다.
\[
\begin{array}{ccccccccccc}
&&&&& 1 &&&&&\\
&&&& 1 && 1 &&&&\\
&&& 1 && 2 && 1 &&&\\
&& 1 && 3 && 3 && 1 &&\\
& 1 && 4 && 6 && 4 && 1 &\\
1 && 5 && 10 && 10 && 5 && 1
\end{array}
\]
분할 정복을 이용한 거듭제곱
분할 정복 방법을 사용하는 거듭제곱 알고리즘은 기본적으로 거듭제곱을 더 작은 부분으로 나누어 처리함으로써 연산의 효율성을 높입니다. 예를 들어, $a^n$을 계산할 때 $n$이 짝수라면 $a^n = (a^{n/2})^2$와 같이 계산하고, 홀수라면 $a^n = a \times a^{n-1}$로 계산합니다. 이 방법은 반복적으로 제곱을 계산함으로써 전체적인 연산 횟수를 줄입니다.
코드 예시:
def power_mod(a, n, mod):
result = 1
base = a % mod
while n > 0:
if n % 2 == 1:
result = (result * base) % mod
base = (base * base) % mod
n //= 2
return result
모듈로 곱셈 역원
모듈로 $m$에서 정수 $a$의 곱셈 역원은 $a \times a^{-1} \equiv 1 \mod m$을 만족하는 $a^{-1}$입니다. 이는 $m$이 소수일 때 페르마의 소정리를 이용하여 쉽게 구할 수 있습니다.
코드 예시:
def mod_inverse(a, m):
return power_mod(a, m-2, m) # 페르마의 소정리 이용
3. 페르마의 소정리
페르마의 소정리에 따르면, $p$가 소수이고 $a$가 $p$의 배수가 아니면, $a^{p-1} \equiv 1 \mod p$가 성립합니다. 이 성질은 모듈로 $p$에서의 역원을 계산할 때 유용하게 사용됩니다.
코드 예시:
def fermat_theorem(a, p):
return power_mod(a, p-1, p)
종합적 코드 예시
def combined_example(a, n, m):
# 거듭제곱
power = power_mod(a, n, m)
# 모듈로 역원
inverse = mod_inverse(a, m)
# 페르마의 소정리 검증
fermat_test = fermat_theorem(a, m)
return {
"power": power,
"mod_inverse": inverse,
"fermat_theorem": fermat_test
}
# 예시 값
a, n, m = 3, 5, 17
result = combined_example(a, n, m)
print(result)
위 코드에서는 주어진 값 $a, n, m$을 사용하여 분할 정복을 이용한 거듭제곱, 모듈로 곱셈 역원, 그리고 페르마의 소정리를 계산하고 결과를 출력합니다.
https://www.acmicpc.net/problem/11401
11401번: 이항 계수 3
자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
www.acmicpc.net
이항 계수 \(\binom{N}{K}\)는 \(N!\)을 \(K!\)와 \((N-K)!\)로 나눈 값을 의미합니다. 이항 계수를 계산할 때 큰 수의 연산을 피하기 위해 모듈로 연산을 사용하는데, 이 경우 페르마의 소정리를 활용한 모듈로 곱셈 역원을 사용하여 계산할 수 있습니다.
문제에서 주어진 대로, 결과를 1,000,000,007 (\(MOD\))로 나눈 나머지를 출력해야 합니다. \(MOD\)는 소수이므로 페르마의 소정리를 적용할 수 있습니다. 페르마의 소정리에 따르면, \(a^{MOD-1} \equiv 1 \mod MOD\)가 성립하며, 이를 이용해 \(a^{MOD-2}\)가 \(a\)의 모듈로 \(MOD\)에서의 역원이 됩니다.
### 풀이 절차
1. \(N!\), \(K!\), \( (N-K)! \)의 팩토리얼 값을 \(MOD\)로 나눈 나머지를 계산합니다.
2. \(K!\)와 \( (N-K)! \)의 모듈로 \(MOD\)에서의 역원을 계산합니다.
3. \(\binom{N}{K} \equiv N! \times (K!)^{-1} \times ((N-K)!)^{-1} \mod MOD\)를 계산합니다.
### 파이썬 코드
MOD = 1000000007
def power_mod(a, n, mod):
result = 1
base = a % mod
while n > 0:
if n % 2 == 1:
result = (result * base) % mod
base = (base * base) % mod
n //= 2
return result
def factorial_mod(n, mod):
result = 1
for i in range(2, n+1):
result = (result * i) % mod
return result
def binomial_coefficient(n, k, mod):
if k > n:
return 0
if k == 0 or k == n:
return 1
fact_n = factorial_mod(n, mod)
fact_k = factorial_mod(k, mod)
fact_n_k = factorial_mod(n-k, mod)
inverse_k = power_mod(fact_k, mod-2, mod)
inverse_n_k = power_mod(fact_n_k, mod-2, mod)
return fact_n * inverse_k % mod * inverse_n_k % mod
n,k = map(int,input().split())
result = binomial_coefficient(n, k, MOD)
print(result)
위 코드는 \(\binom{N}{K}\)를 계산하여 \(MOD\)로 나눈 나머지를 출력합니다. 큰 수의 팩토리얼을 계산하는 과정에서 시간과 메모리 효율성을 위해 \(MOD\)를 적용하였습니다. \(MOD\)가 소수라는 사실을 이용하여 모듈로 곱셈 역원을 계산하는 `power_mod` 함수를 사용하였습니다.