[정답이 아니라 풀이 기록입니다.]
여러 쿼리가 들어온다. 쿼리마다 n와 k가 주어질 때 nCk를 계산하여라.
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!을 구했으니 다음으로 중 나누는 부분인 입니다.
그런데 모듈러 연산은 나눗셈에 적용되지 않습니다.
그렇기에 나눗셈 대신 역원(역수)인 를 곱해봅시다.
페르마 소정리에 의해
(p는 소수)
이것을 우리가 쓰는 나머지 연산으로 대충 변경해봅시다.
양변을 a로 나눠줍니다.
자세한 정의는 저도 모르지만 a의 (p-2)제곱을 p로 나눈 나머지가 a의 역원(역수)과 같네요
a에 p에 MOD를 넣어봅시다.
(MOD는 문제에서 주어졌듯 소수입니다)
오른쪽 항이 이네요.
그렇기에 으로 나누는 대신 왼쪽항을 n!에 곱해주면 답을 구할수 있습니다.
를 구해봅시다.
이 쓰기 어려우므로 일단 로 두고 진행합니다.
가 있을때 이를 구하는 방법은 일단 a를 b번 곱하는 방법이 있습니다.
= a * a * a * ....
이것의 시간복잡도는 대략 O(b)이겠네요.
그런데 이문제에서는 MOD가 매우 크기에 너무 오래 걸립니다.
그렇기에 좀 더 빠른 방법으로 분할정복을 이용합니다.
=
이렇게 a^b이 반으로 나눠서 계산 할 수 있음을 이용하여 분할정복을 계산하는 것을
분할정복 거듭제곱이라 합니다.
이것의 시간 복잡도는 대략 O(log b) 입니다.
함수를 하나 만듭니다.
long long Power(long long n) / a의 n거듭제곱을 반환합니다.
이 함수는 3가지 분기로 작동합니다.
- n==1
return a
- n % 2 == 0
long long c = Power(n/2)
return ((c % MOD) * ( c % MOD )) % MOD- 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변수에 미리 를 대입해 둡니다.
a = ((fac[k] % MOD) * (fac[n-k] % MOD)) % MOD;
printf("%lld\n",((fac[n] % MOD) * (POWER(MOD-2) % MOD)) % MOD);
이것을 쿼리마다 반복하면 됩니다.
백준 하면서 페르마의 소정리, 모듈러 역원 들어간 문제 딱 2개 풀어봤습니다.
조금 마이너한 부류인가 싶기도 하네요.