[백준]13977 이항 계수와 쿼리

K_Gs·2022년 4월 6일
0

BOJ

목록 보기
3/13
post-thumbnail

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

이항 계수와 쿼리

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

접근

  1. nCk는 n!/(k!(nk)!)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!(nk)!)n! / (k! * (n-k)!) 중 나누는 부분인 /(k!(nk)!)/ (k! * (n-k)!) 입니다.
그런데 모듈러 연산은 나눗셈에 적용되지 않습니다.

그렇기에 나눗셈 대신 역원(역수)(k!(nk)!)1(k! * (n-k)!)^{- 1}를 곱해봅시다.

페르마 소정리에 의해
ap11 (MOD p)a^{p-1}\equiv 1\ (MOD \ p) (p는 소수)
이것을 우리가 쓰는 나머지 연산으로 대충 변경해봅시다.
ap1 %  p=1a^{p-1}\ \% \ \ p = 1
양변을 a로 나눠줍니다.
ap2 %  p=a1a^{p-2}\ \% \ \ p = a^{-1}

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

a에 (k!(nk)!)(k! * (n-k)!) p에 MOD를 넣어봅시다.
(MOD는 문제에서 주어졌듯 소수입니다)

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

오른쪽 항이 (k!(nk)!)1(k! * (n-k)!)^{-1} 이네요.
그렇기에 (k!(nk)!)(k! * (n-k)!)으로 나누는 대신 왼쪽항을 n!에 곱해주면 답을 구할수 있습니다.

거듭 제곱

(k!(nk)!)MOD2 %  MOD(k! * (n-k)!)^{MOD - 2} \ \% \ \ MOD를 구해봅시다.
(k!(nk)!)(k! * (n-k)!)이 쓰기 어려우므로 일단 aa로 두고 진행합니다.

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

aba^b = a * a * a * ....

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

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

aba^b = ab/2ab/2a^{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!(nk)!)(k! * (n-k)!)를 대입해 둡니다.

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

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

마무리

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

profile
~(~o~)~

0개의 댓글