문제
풀이
이항 계수에 moduler 연산을 하는 문제이다. N과 K의 범위가 4,000,000(4백만)이나 되기 때문에 factorial을 구하면 long long 범위를 훨씬 넘는다. (20!조차도 long long 범위를 넘는다고 한다.
nCk = n! / (k! * (n-k)!) 이다. 그러므로 이 문제에서는 n! / (k! * (n-k)!) mod P를 구하면 되는 문제이다.
moduler 연산은 덧셈과 곱셈에 대해서 각각 (a+b) mod P = ((a mod P) + (b mod P)) mod P, (a*b) mod P = ((a mod P) * (b mod P)) mod P이다. 그러나, 문제에서 구하고자 하는
나눗셈에 대해서는 단순하게 (a/b) mod P != ((a mod P) / (b mod P) mod P 이다. 그래서 곱셈식으로 바꿔주어 역원을 구하는 식으로 moduelr 연산을 해야만 한다.
결과적으로 문제에서는 ((n! mod P) * ((k!(n-k)!)^(-1) mod P)) mod P 을 구하면 된다. (k!(n-k)!)^(-1) mod P 를 구하는게 핵심인데 이 때 나오는게 페르마의 소정리이다.
간단하게 말해서 p가 소수라면, a mod P 의 역원(a^(-1) mod P)은 a^(p-2) mod P 라는 것이다. 그러므로, (k!(n-k)!)^(-1) mod P은 (k!(n-k)!)^(P-2) mod P로 바꿀 수 있다.
결과적으로 재귀함수를 통해서 factorial연산을 하고, 거듭제곱을 1629번 문제 곱셈 문제에서 푼대로 분할 정복을 통해서 연산하면 최종 답을 구할 수 있다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
long long factorial(long long a){
long long fac = 1;
while(a>1){
fac = fac * a % MOD;
a--;
}
return fac;
}
long long pow(long long x, long long y){
if(y==1){
return x%MOD;
}
else{
long long temp = pow(x, y/2);
if(y%2 == 1){
return ((temp * temp % MOD)* x)%MOD;
}
else return (temp * temp)%MOD;
}
}
int main(){
long long n, k;
scanf("%lld %lld", &n, &k);// nCk = n!/(k!)/(n-k)!
long long numer = factorial(n)%MOD;
long long denom = factorial(k)*factorial(n-k)%MOD;
printf("%lld\n", (numer*pow(denom, MOD-2))%MOD);
}
