combination

이항계수 (조합)

알아두어야 할 자료형 범위

15!의 경우 int 범위를 벗어난다

21!의 경우 long long을 벗어난다

파스칼의 삼각형

int combi(int n, int k) {
	if (k == 0 || n == k) return 1;

	// case_choose + case_not_choose
	return combi(n - 1, k - 1) + combi(n - 1, k);
}

그러나 이 경우 같은 n, k에 이미 구한 값을 다시 계산해서 이용하므로 시간 복잡도가 증가한다.

따라서 이를 해결하기 위해 메모이제이션을 사용한다.

메모이제이션을 이용하는 방법

// first : n, second : k;
int memo[1000][1000];

int combi(int n, int k) {
	if (memo[n][k] != 0) {
		return memo[n][k];
	}

	if (k == 0 || n == k) { 
		memo[n][k] = 1;
		return 1; 
	}

	// case_choose + case_not_choose
	int sum = combi(n - 1, k - 1) + combi(n - 1, k);
	memo[n][k] = sum;

	return sum;
}

정답에 나머지 연산이 들어가야 하는 경우

int combi(int n, int k) {
	if (memo[n][k] != 0) {
		return memo[n][k];
	}

	if (k == 0 || n == k) { 
		memo[n][k] = 1;
		return 1; 
	}

	// case_choose + case_not_choose
	int sum = combi(n - 1, k - 1) + combi(n - 1, k);
	sum %= diff;
	memo[n][k] = sum;

	return sum;
}

합동식에 의해 나머지 연산을 저렇게 할 수 있다.

(a+b)%c = (a%c+b%c)%c 이기 때문이다

ar = a%c, br = b%c 라고 하고,

sumr = (a+b)%c 라고 하자

(a+b)%c = sumr = (ar + br)%c 이다

여기서 ar+br이 c를 초과할 수 있다.