[백준] 11401번: 이항 계수 3

문제

https://www.acmicpc.net/problem/11401

풀이

먼저 두 가지 개념을 알아야 한다.

모듈로 곱셈 역원

$a \cdot x \equiv 1 \,(mod \,m)$

다음 합동식을 만족하는 정수 $x$ 를 $a$의 모듈로 $m$에 대한 곱셈 역원이라고 한다. 단, $a$와 $m$은 서로소여야 한다.

다르게 해석하면, $a$와 $x$의 곱을 $m$으로 나눈 나머지가 1이 되게 하는 $x$를 말한다.

페르마의 소정리

$a^{p-1} \equiv 1 \, (mod\,p)$

$p$는 소수, $a$는 정수이며, $a$와 $p$는 서로소일 때, 위 합동식을 만족한다.

모듈로 곱셈 역원과 페르마의 소정리를 통해 이항 계수를 계산해보자.

이항 계수

공식은 다음과 같다.

$_nC_r = \frac{n!}{(n-k)!\cdot k!}$

문제에서는 이항 계수의 결과를 1,000,000,007로 나눈 나머지를 구해야 한다. $p=1,000,000,007$ 라고 할 때, 다음 합동식을 만족한다.

$_nC_r \equiv n! \cdot (k! \cdot (n-k)!)^{-1} \, (mod \, p)$

모듈로 연산에서는 나눗셈이 정의되지 않으므로 $(n-k)! \cdot k!$의 역원을 곱하는 방식으로 작성해야 한다.

그렇다면 $(n-k)! \cdot k!$의 역원은 어떻게 구해야 하는가? 여기서 페르마의 소정리를 사용한다.

$a^{p-1} \equiv 1 \, (mod\,p)$

양변을 $a$로 나눈다.

$a^{p-2} \equiv a^{-1} \, (mod\,p)$

즉, $a^{-1}$의 역원은 $a^{p-2}$이다. $a$에 $(n-k)! \cdot k!$을 대입하면, $(n-k)! \cdot k!$의 역원은 $((n-k)! \cdot k!)^{p-2} \, (mod \, p)$가 된다.

다시 이항 계수 공식에 대입하면, 아래와 같다.

$_nC_r \equiv n! \cdot (((n-k)! \cdot k!) \, (mod \, p))^{p-2} \, (mod \, p)$

다음 순서로 답을 계산한다.

1. $n!\,(mod\,p)$ 를 구한다.
2. $(n-k)! \cdot k!\,(mod\,p)$ 를 구한다.
3. 2번 수를 $p-2$번 거듭제곱한다. 이 때 분할 정복을 사용한다.
4. 1번과 3번 수를 곱한 값을 다시 $p$에 대한 모듈로 연산을 진행한다.

코드

C++

#include <iostream>

#define MOD 1000000007

using namespace std;

long long fact[4000001];

long long divconq(long long a, int r) {
	if (r == 0) return 1;

	long long half = divconq(a, r / 2);
	long long ret = (half * half) % MOD;

	if (r % 2 == 1) ret = (ret * a) % MOD;

	return ret;
}

int main() {
	int n, k;
	cin >> n >> k;

	fact[0] = 1;
	for (int i = 1; i <= n; i++) {
		fact[i] = fact[i - 1] * i;
		fact[i] %= MOD;
	}
	
	cout << (fact[n] * divconq((fact[n - k] * fact[k]) % MOD, MOD - 2)) % MOD;
}

시간복잡도

팩토리얼 계산에서 $O(N)$, 분할 정복에서 $O(MOD)$ 이다. $log_2{1000000007}$ 은 약 30이므로, 사실 상 상수 시간 시간복잡도를 가진다고 할 수 있다.

공간복잡도

공간복잡도는 fact 배열에서 $O(N)$이다.

fact 배열은 long long 타입 4000001개의 데이터를 담을 수 있으므로, 8 X 4000001 = 약 30MB 크기를 가진다.

분할 정복에서 재귀 깊이는 깊지 않으므로 스택 메모리는 거의 차지하지 않는다.