[백준 11051] 이항계수 2

문제 링크 => 11051번: 이항 계수 2 (acmicpc.net)

11051번: 이항 계수 2

 

다이나믹 프로그래밍 문제이다.

 

C(N, K) 를 이항계수 N(N-1)...(N-K+1) / 1*2*...*K 라고 할 때 Optimal substructure는 다음과 같다.

 

K = 0  =>  C(N, K) = 1

 

K != 0  =>  C(N, K) = C(N, K-1) * (N - K + 1) / K % 10007

 

이 때 나누기 연산이 좀 거슬려 보인다.

 

여기서 10007은 prime 임을 이용하여 fermat's theorem 을 이용해 보도록 하자.

 

x^(m-1) % m = 1 (이때 m은 prime)

 

x * x^(m-2) % m = 1 이므로 x^-1 = x^(m-2) % m 임을 알 수 있다.

 

즉, C(N, K) = C(N, K-1) * (N - K + 1) * (K^(10005) % 10007) % 10007 이다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int dp[1001][1001];

int f(int x, int y) {
	if (y == 0) return 1;
	if (y == 1) return x;
	int ret = f(x, y / 2);
	if (y % 2 == 0) return (ret * ret) % 10007;
	ret = (ret * ret) % 10007;
	return (x * ret) % 10007;
}

int solution(int N, int K) {
	int i;

	dp[N][0] = 1; // set table
	for (i = 1; i <= K; i++) {
		dp[N][i] = ((dp[N][i - 1] == 0 ? 10007 : dp[N][i - 1])
			* (N - i + 1)) % 10007;
		dp[N][i] = (dp[N][i] * f(i, 10007 - 2)) % 10007;
	}

	return dp[N][K];
}

int main(int argc, char* argv[]) 
{
	int N, K;

	scanf("%d %d", &N, &K);
	printf("%d", solution(N, K));

	return 0;
}