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를 초과할 수 있다.

페르마의 소정리를 사용한 방법

long long myPow(long long base, long long expo) {
  long long result = 1;

  while (expo > 0) {
    if (expo % 2 == 1) {
      result *= base;
      result %= MOD;
    }
    base = (base * base) % MOD;
    expo /= 2;
  }
  return result;
}

// 페르마의 소정리를 이용한 nCk 를 구하는 함수
long long combi(int n, int k) {
  if (k > n || k < 0) return 0;
  if (k == 0 || k == n) return 1;

  long long numer = factorial[n] % MOD;
  long long denom = (factorial[k] * factorial[n - k]) % MOD;

  return numer * myPow(denom, MOD - 2) % MOD;
};