[BOJ]13977 이항 계수와 쿼리

[정답이 아니라 풀이 기록입니다.]

이항 계수와 쿼리

여러 쿼리가 들어온다. 쿼리마다 n와 k가 주어질 때 nCk를 계산하여라.

접근

1. nCk는 $n! / (k! * (n-k)!)$
2. nCk를 주어진 수로 나눈 나머지를 출력해야합니다.
3. n,k가 크기 때문에 모든 답을 구하고 나머지를 구할 수 없습니다.

구현

n, k가 크기 때문에 연산 중간중간에 모듈러 연산을 넣어서 나머지를 구해야합니다.

(나누는 수는 미리 주어지기에 MOD 라는 상수로 정의 해 두겠습니다.)

팩토리얼의 전처리

일단 nCk의 표현에 팩토리얼이 사용되기 때문에 미리 처리를 해둬야 합니다.
팩토리얼은 20! 이후부터 long long의 범위를 넘어가지만 모듈러 연산을 사용할 것이기에
n!의 나머지만 구해도 됩니다.

long long fac[4000002];
fac[0] = 1;

for(long long i = 1 ; i<= 4000000; i++){
	fac[i] = ( (fac[i-1] % MOD) * (i % MOD) ) % MOD;
}

이렇게 fac[i]에 i!의 나머지가 저장되었습니다.
조합의 표현에서 n!은 여기서 그냥 꺼내다 쓰면 됩니다.

모듈러 나눗셈?

n!을 구했으니 다음으로 $n! / (k! * (n-k)!)$

그렇기에 나눗셈 대신 역원(역수)인 $(k! * (n-k)!)^{- 1}$

페르마 소정리에 의해
$a^{p-1}\equiv 1\ (MOD \ p)$

자세한 정의는 저도 모르지만 a의 (p-2)제곱을 p로 나눈 나머지가 a의 역원(역수)과 같네요

a에 $(k! * (n-k)!)$

$(k! * (n-k)!)^{MOD - 2} \ \% \ \ MOD = (k! * (n-k)!)^{- 1}$

오른쪽 항이 $(k! * (n-k)!)^{-1}$

거듭 제곱

$(k! * (n-k)!)^{MOD - 2} \ \% \ \ MOD$

$a^b$가 있을때 이를 구하는 방법은 일단 a를 b번 곱하는 방법이 있습니다.

$a^b$ = a * a * a * ....

이것의 시간복잡도는 대략 O(b)이겠네요.
그런데 이문제에서는 MOD가 매우 크기에 너무 오래 걸립니다.

그렇기에 좀 더 빠른 방법으로 분할정복을 이용합니다.

$a^b$ = $a^{b/2} * a^{b/2}$

이렇게 a^b이 반으로 나눠서 계산 할 수 있음을 이용하여 분할정복을 계산하는 것을
분할정복 거듭제곱이라 합니다.
이것의 시간 복잡도는 대략 O(log b) 입니다.

분할정복 거듭제곱 구현

함수를 하나 만듭니다.

long long Power(long long n) / a의 n거듭제곱을 반환합니다.

이 함수는 3가지 분기로 작동합니다.

1. n==1

   return a

2. n % 2 == 0

   long long c = Power(n/2)
   return ((c % MOD) * ( c % MOD )) % MOD

3. n % 2 == 1

   long long c = Power(n-1)
   return ((c % MOD) * ( a % MOD )) % MOD

a는 전역함수로 만들어 둡니다.

long long a;

long long Power(long long n) {
	if (n == 0) {
		return 1;
	}
	else if (n == 1) {
		return a;
	}
	else if (n % 2 == 0) {
		long long c = Power(n/2)
		return ((c % MOD) * ( c % MOD )) % MOD
	}
	else {
		long long c = Power(n-1)
		return ((c % MOD) * ( a % MOD )) % MOD
	}
}	

답 출력

이제 위의 조합식대로 그대로 모듈러 연산을 포함해 구현하고 출력합니다.
이때 거듭제곱을 위해 정의해둔 a변수에 미리 $(k! * (n-k)!)$

	a = ((fac[k] % MOD) * (fac[n-k] % MOD)) % MOD;
	printf("%lld\n",((fac[n] % MOD) * (POWER(MOD-2) % MOD)) % MOD);

이것을 쿼리마다 반복하면 됩니다.

마무리

백준 하면서 페르마의 소정리, 모듈러 역원 들어간 문제 딱 2개 풀어봤습니다.
조금 마이너한 부류인가 싶기도 하네요.