POW연산을 수행할 때 지수가 최대 4000000까지 입력이 가능하다. 따라서 일반적인 연산으로는 시간 초과가 발생한다. 이를 두배로 적용시켜 분할 정복하는 power 함수를 만들어 해결한다. 2^22 = 4194304의 값을 가진다. 하나씩 곱셈하는 식으로 power 연산을 구현하면 최대 4000000번 수행해야 하는 연산 횟수를 최대 22번으로 줄어들도록 구현할 수 있다.
위의 식을 정리하면 분모에 k! 이 남게 된다. 분모의 k! 에 모듈로 연산을 적용하기 위해서는 역원을 구하는 과정이 필요하다. 이를 페르마의 소정리와 함께 적용하면 역원을 구하여 모듈로 연산을 수행할 수 있다.
페르마의 소정리 p 가 소수이면, 모든 정수 a에 대해 아래 식을 따른다.
혹은 p가 소수이고 a가 p의 배수가 아니면, 아래 식을 따른다.
문제에서 주어진 1000000007은 소수이다. 주어지는 N과 K는 4000000 이하이므로 MOD 값을 넘지 않기 때문에 배수가 될 수 없다. 따라서 페르마의 소정리의 두 번째 경우를 적용할 수 있다.
역원 구하는 과정
위의 페르마의 소정리에 의해 아래 식이 성립한다.
어떤 값에 1을 곱해도 모듈로 연산 결과 역시 같다는 성질을 이용하여 양변에 (k!)^-1을 곱하면 아래 식을 따른다.
최종적으로 우리가 구할 계산은 아래와 같아진다.
위 식을 앞서 만든 빠른 power 함수와 factorial을 수행하여 연산하면 결과를 얻을 수 있다.
소스 코드
#include <iostream>
using namespace std;
const int MOD = 1000000007;
long long n,k;
long long fact(long long st, long long end){
long long ret = 1;
for(int i=st; i<=end; i++){
ret = ret * i % MOD;
}
return ret;
}
long long power(int a, int b){
if(b==1) return a % MOD;
long long half = power(a,b/2);
if(b%2==1){
return half*half%MOD * a%MOD;
}
else{
return half*half%MOD;
}
}
int main(){
cin >> n >> k;
long long ans = fact(n-k+1,n) * power(fact(1,k), MOD-2) % MOD;
cout << ans;
return 0;
}
결과 및 후기
페르마의 소정리와 역원 구하는 과정을 암호학 시간에 배웠던 기억이 났다. 그와 관련되어 shift 하며 (결국 2배) 빠르게 연산하는 함수, 최대 공약수를 구할 때 사용되는 유클리드 알고리즘 등을 다시 복습해보게 하는 문제여서 좋았다.
