문제접근🤔

이항계수

$$ nC_k = {{n-1}C_{k-1} + _{n-1}C_k \quad (0<k<n) \choose 1 \quad(k = 0 \ or \ k=n)} $$

놓쳤던 부분😅

% 10007을 어디서 할거냐가 중요한데, $_nC_k = {n!\over (n-k)!k!}$ 의 공식을 이용하게 되면

다음과 같은 문제가 생길 수 있다.

n! % 10007과 (n-k)! % 10007의 경우에서 전자의 경우에서 10007을 넘고 후자의 경우에서 10007을 넘지 않는 경우 이상한 값을 초래한다

코드😁

5932 KB

4 ms

#include <iostream>

int n, k;
int dp[1001][1001];

void input_setting()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	std::cin >> n >> k;
}

void solution()
{
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= k; j++)
		{
			if (i == j || j == 0)
				dp[i][j] = 1;
			else
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007;
		}
}

void print()
{
	std::cout << dp[n][k];
}

int main(void)
{
	input_setting();
	input();
	solution();
	print();
	return (0);
}