이항 계수

순열과 조합에 대해서 알아야 한다. 예를들어 색깔이 다른 공 $n$개에서 $k$ 개를 선택할 때 순서를 고려해 뽑는 경우는 순열이고, 순서를 고려하지 않고 뽑는 경우는 조합이다.

• 순서를 고려해서 뽑는 경우 $_nP_k = \frac{n!}{(n - k)!}$
• 순서를 고려하지 않는 경우 $_nC_k = \frac{n!}{(n-k)!k!}$

순열과 조합 중 조합에대해 구현해본다.

제한이 작을 때

$n$과 $k$의 제한이 작은 경우 $_nC_k = \frac{n!}{(n-k)!k!}$ 공식 그대로 구현할 수 있다.

#include <iostream>

int main()
{
	int N = 0, K = 0;
	std::cin >> N >> K;

	int Result = 1;
	for (int i = 1; i <= N; ++i) Result *= i;
	for (int i = 1; i <= K; ++i) Result /= i;
	for (int i = 1; i <= N - K; ++i) Result /= i;
	std::cout << Result;
	return 0;
}

6 3
20

제한이 클 경우

제한이 클 경우 다음 조합의 성질을 이용할 수 있다.

$$ _nC_k = _{n-1}C_k + {n-1}C{k-1} $$

위 성질과 DP를 이용할 수 있다.

Comb[i][j] = $_iC_j$ 라고 하면 Comb[i][j] = Comb[i - 1][j] + Comb[i - 1][j - 1] 라는 식을 얻을 수 있다. int 오버플로에 주의해서 코드를 작성하면 다음과 같다.

#include <iostream>
#include <vector>

int main()
{
	int N = 0, K = 0;
	std::cin >> N >> K;

	int Mod = 10007; // int 오버플로 방지
	std::vector<std::vector<int>> Comb(N + 1, std::vector<int>(N + 1, 0));
	for (int i = 1; i <= N; ++i)
	{
		Comb[i][0] = Comb[i][i] = 1;
		for (int j = 1; j < i; ++j)
			Comb[i][j] = (Comb[i - 1][j] + Comb[i - 1][j - 1]) % Mod;
	}

	std::cout << Comb[N][K];
	return 0;
}

1000 500
40940