백준 11401, 이항 계수 3

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 nCk를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

출력

nCk를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

5 2

예제 출력

10

  처음에 이 문제에 대해서 접근할 때는 동적 프로그래밍(Dynamic Programming)을 이용하여 최대한 잡아 먹는 메모리를 줄이면서 문제를 해결하고자 하였다. 이항 계수를 구하기만 하면 나머지를 구하는 것은 무척 쉬운 일이라고 생각했다. 다음과 같이 문제를 해결하고자 하였다.

1. 아무 것도 고르지 않은 경우에 대해서 1을 반환하고 이를 조합 리스트에 저장한다.
2. 만약 조합 리스트에 출력하고자 하는 값이 있다면 그대로 반환한다.
3. 리스트에도 반환할 값이 없다면  (k-1)개를 고르는 경우에 (n-k+1)/k를 곱한 값을 리스트에 저장하고, 이를 반환한다.

 코드는 다음과 같다

#include <iostream>
unsigned long long int DP[40000000] = {0, };
unsigned long long int getBiCo(unsigned long long int n, unsigned long long int k) {
	if (k == 0) {
		DP[k] = 1;
		return 1;
	}
	else if (DP[k]!= 0) {
		return DP[k];
	}
	else {
		DP[k] = getBiCo(n, k-1)*(n-k+1)/k;
		return DP[k];
	}
}
int main() {
	int N, K;
	std::cin >> N >> K;
	std::cout << getBiCo(N, K) % 1000000007;
	return 0;
}

 일단은 문제에서 원하는 답을 얻었지만, 메모리 조건에 부합하지 않아 틀렸다. 동적 프로그래밍 기법을 사용한다 하더라도 결국 값이 커지면 메모리를 많이 잡아먹는 것은 같다. 특히 이번 문제의 경우 말그대로 입력이 한 없이 커질 수 있어서 적합하지 않은 것 같다.

 도저히 감을 못 잡겠어서 정답을 찾아보니까 페르마의 소정리를 이용하여야 한다고 나와 있었다. 일단 모듈러 연산을 이항 계수의 정의식에 바로 적용할 수는 없다. 밑의 분모 때문에 적용을 못하기 때문이다. 페르마의 소정리는 다음과 같다.

그래서 다음과 같은 식이 성립한다.

이제는 분모 부분이 정수로 치환되면서 이제는 계산이 가능해진다. 거듭제곱의 경우는 분할 정복을 이용하면 O(logN)으로 해결이 가능하고, 팩토리얼 연산의 경우 O(N) 으로 해결이 가능하다고 한다. 코드는 다음과 같다.(처음 보는 유형이라서 사실상 코드를 거의 배꼈다 ㅠ..)

#include <iostream>
#include <cmath>

unsigned long long N, K, A, B, half;
unsigned long long mod = 1000000007;

unsigned long long solve(unsigned long long int x) {
	if (x == 0) return 1;
	if (x % 2 == 1) return B * solve(x - 1) % mod;
	else {
		half = solve(x/2);
		return half * half % mod;
	}
}

int main() {

	std::cin >> N >> K;
	A = 1;
	for (int i = N; i >= N - K + 1; i--)A = (A * i) % mod;
	B = 1;
	for (int i = 1; i <= K; i++) B = (B * i) % mod;

	B = solve(mod-2);

	std::cout << A * B % mod;

	return 0;
}

대충은 이해했는 데 모듈 연산에 대해서는 좀 더 공부해 볼 필요가 있을 것 같다. 처음에 이해할 때, 모듈 연산의 기본적인 성질을 몰라서 이해하는 데 시간이 걸렸다. 결과적으로 이 문제는 팩토리얼 함수 구현, 거듭제곱(분할 정복)의 구현, 페르마의 소정리로 이루어져 있었다. 거듭 제곱의 분할 정복 구현은 한 번 다루어 볼 필요가 있겠다는 생각이 들었다.