[백준 11401][C++] 이항 계수 3

문제

https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

 

풀이 과정

이 문제는 중요 포인트가 두 가지 있었다.

 

(1) 분할 정복으로 연산 시간 감소

POW연산을 수행할 때 지수가 최대 4000000까지 입력이 가능하다. 따라서 일반적인 연산으로는 시간 초과가 발생한다. 이를 두배로 적용시켜 분할 정복하는 power 함수를 만들어 해결한다. 2^22 = 4194304의 값을 가진다. 하나씩 곱셈하는 식으로 power 연산을 구현하면 최대 4000000번 수행해야 하는 연산 횟수를 최대 22번으로 줄어들도록 구현할 수 있다.

 

(2) 모듈로 곱셈의 분수 처리(역원 처리)

모듈로 연산에 대해서 잘 모른다면 위키피디아 및 다른 자료를 참고 바란다. [위키피디아 : 모듈로 연산]

 

이 문제는 최종적으로 아래의 식을 계산하는 문제이다. 

 

위의 식을 정리하면 분모에 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배) 빠르게 연산하는 함수, 최대 공약수를 구할 때 사용되는 유클리드 알고리즘 등을 다시 복습해보게 하는 문제여서 좋았다.